Back to: Python Data Structure and Algorithims

🌲 Understanding Preorder Depth-First Search (DFS) in Binary Trees

In this section, we’ll begin exploring Depth-First Search (DFS) — one of the most important traversal techniques for trees.

Earlier, we discussed Breadth-First Search (BFS), where we move through the tree level by level.
Now, we’ll shift our focus to DFS, where we go as deep as possible down one branch before backtracking.

🧠 What Is Depth-First Search?

In Depth-First Search (DFS), we explore each branch of the tree deeply before moving on to the next.

There are three common ways to perform DFS:

Preorder Traversal
Inorder Traversal
Postorder Traversal

We’ll begin with the Preorder Traversal in this article.

🌿 What Is Preorder Traversal?

In Preorder DFS, the order in which we visit the nodes is:

Root → Left Subtree → Right Subtree

That means for every node:

Visit (or record) the current node’s value first.
Traverse the left subtree completely.
Finally, traverse the right subtree.

🌳 Example Tree

Let’s consider this binary tree:

        47
       /  \
     21    76
    / \    / \
   18 27  52 82

Now, let’s trace how Preorder Traversal works here.

🪜 Step-by-Step Preorder Traversal

Let’s start at the root and follow the Root → Left → Right pattern.

Step 1: Start at the Root (47)

Visit 47 and add it to the list.

Result: [47]

Step 2: Move Left (to 21)

Visit 21 and add it to the list.

Result: [47, 21]

Step 3: Keep Moving Left (to 18)

Visit 18 and add it to the list.

Result: [47, 21, 18]

There’s no further left node from 18, so we backtrack.

Step 4: Move Right of 21 (to 27)

Visit 27 and add it to the list.

Result: [47, 21, 18, 27]

We’ve now visited everything under 21.
Time to go back to the root and move right.

Step 5: Move Right of 47 (to 76)

Visit 76 and add it to the list.

Result: [47, 21, 18, 27, 76]

Now, following DFS rules, we go left first.

Step 6: Move Left of 76 (to 52)

Visit 52 and add it to the list.

Result: [47, 21, 18, 27, 76, 52]

No left or right child here, so backtrack to 76.

Step 7: Move Right of 76 (to 82)

Visit 82 and add it to the list.

Result: [47, 21, 18, 27, 76, 52, 82]

✅ Final Preorder Traversal Result:

[47, 21, 18, 27, 76, 52, 82]

🧩 Visualization of Preorder Process

If we trace the traversal visually, the order of visiting nodes (47 → 21 → 18 → 27 → 76 → 52 → 82)
exactly represents the Preorder sequence — visiting the root first, then exploring left before right at every step.