Back to: Python Data Structure and Algorithims

💻 Coding Preorder Depth-First Search (DFS) with Recursion — Step-by-Step

Now that we understand how Preorder Depth-First Search (DFS) works conceptually,
let’s move on to coding it.

We’ll use the same binary tree as before and see how recursion and the call stack help us navigate through the nodes.

🌳 The Tree We’re Using

Here’s the binary tree again for reference:

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

🧩 Step 1: Define the Method

Inside the Binary Search Tree class, we’ll define our method called DFS_preorder.
We’ll also create an empty list called results to store the traversal output.

def DFS_preorder(self):
    results = []

    def traverse(node):
        # Step 1: Record the current node’s value
        results.append(node.value)

        # Step 2: Recurse left
        if node.left:
            traverse(node.left)

        # Step 3: Recurse right
        if node.right:
            traverse(node.right)

    traverse(self.root)
    return results

🔄 Step 2: Understand the Recursive Flow

The inner function traverse() is the heart of the recursion.
It takes a node, adds its value to the list, and then recursively calls itself for the left and right children.

Here’s the process visualized step-by-step:

🪜 Step 3: Start the Traversal

We begin by calling:

traverse(self.root)

This passes the root node (47) into the recursive function.

The call stack now contains:

traverse(47)

The first action — append 47 to results.

results = [47]

Then it looks left — so we call traverse(21).

🧠 Step 4: Call Stack in Action

Now, traverse(21) is pushed onto the call stack.

Call Stack:
→ traverse(21)
  traverse(47)

We’re now working with node 21.

Append 21 to results
→ [47, 21]
Go left → traverse(18) is called.

🧱 Step 5: Go Deeper to the Left (Node 18)

Push traverse(18) to the stack.

Call Stack:
→ traverse(18)
  traverse(21)
  traverse(47)

Visit node 18:

Append 18 → [47, 21, 18]

There’s no left or right child here.
So, traverse(18) completes and is popped off the stack.

🔁 Step 6: Backtrack to Node 21

We return to node 21, which still has a right child (27).

Call traverse(27)
Append 27 → [47, 21, 18, 27]

27 has no children, so we pop it off the stack.

Then we also pop 21, as both its left and right sides are done.

🌿 Step 7: Back to Root (47)

Now we’re back at 47.
Left is done — time to go right.

Call traverse(76)
Append 76 → [47, 21, 18, 27, 76]

🧩 Step 8: Explore the Right Subtree (76)

76 has two children:

Left → 52
Right → 82

So, call traverse(52):

Append 52 → [47, 21, 18, 27, 76, 52]
No children → Pop it off.

Then call traverse(82):

Append 82 → [47, 21, 18, 27, 76, 52, 82]
No children → Pop it off.

Now we can pop 76.

🏁 Step 9: End of Traversal

Finally, we return to 47.
Both left and right have been explored, so we pop it from the stack too.

Nothing left to process — recursion is complete.

✅ Final result:

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

🧠 Recap of the Call Stack Behavior

Step	Current Node	Stack State (Top → Bottom)	Result List
1	47	[47]	[47]
2	21	[21, 47]	[47, 21]
3	18	[18, 21, 47]	[47, 21, 18]
4	Pop 18	[21, 47]	[47, 21, 18]
5	27	[27, 21, 47]	[47, 21, 18, 27]
6	Pop 27, 21	[47]	[47, 21, 18, 27]
7	76	[76, 47]	[47, 21, 18, 27, 76]
8	52	[52, 76, 47]	[47, 21, 18, 27, 76, 52]
9	82	[82, 76, 47]	[47, 21, 18, 27, 76, 52, 82]

🧾 Final Python Code in Context

Here’s what the complete DFS Preorder method looks like inside a Binary Search Tree class:

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def DFS_preorder(self):
        results = []

        def traverse(node):
            results.append(node.value)
            if node.left:
                traverse(node.left)
            if node.right:
                traverse(node.right)

        traverse(self.root)
        return results

When you build the tree and run this method,
you’ll get the output:

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

🎯 Key Takeaways

Preorder DFS follows the rule: Root → Left → Right
Recursion naturally uses the call stack to track traversal state.
Each function call represents one active node being processed.
Once both left and right are visited, the function returns (pops) from the stack.