Depth First Search (DFS) in Trees

# CHAPTER 6

Depth First Search (DFS) in Trees #

1. Introduction #

2. Learning Objectives #

• Understand the "Maze Runner" plunging philosophy of DFS.

• Define how System Recursion creates a hidden memory Stack.

• Convert a Recursive DFS algorithm into an Iterative DFS algorithm using a manual Stack.

• Trace the backtracking execution flow of a DFS engine.

3. The Core Concept: The Stack (LIFO) #

When an algorithm encounters a fork in the road (e.g., a node with both a Left and Right child), it must explore one path while pausing the other.

1. 1. It physically pushes the Right child onto the memory Stack for "safekeeping."

1. 2. It aggressively plunges down the Left child's path.

1. 3. When the Left path hits a dead-end Leaf (null), the algorithm turns around, pops the top node off the Stack (the paused Right child), and begins exploring it.

4. Recursive DFS vs. Iterative DFS #

1. Recursive DFS (The OS Stack): When you write a recursive function (a function that calls itself), you do not need to manually write array code to create a Stack. The computer's Operating System automatically allocates a hardware Call Stack. Every time the function calls itself, the OS creates a physical RAM frame pausing the current function state, allowing it to seamlessly backtrack when the inner function returns. *(This is how our Chapter 5 traversal code worked in just 3 lines!).*

2. Iterative DFS (The Manual Stack): Recursion is beautiful but dangerous. If a tree is 100,000 nodes deep, the OS Call Stack will overflow and crash the server (StackOverflowError). Enterprise code often requires rewriting recursion as an iterative while loop utilizing a manually declared Stack object.

5. Step-by-Step Iterative DFS (Preorder) #

The Algorithm:

1. 1. Create an empty Stack. Push the Root node into it.

1. 2. Loop while the Stack is not empty.

1. 3. Pop the top node. Print its value.

1. 4. CRITICAL: Push the Right child into the Stack first, then push the Left child. (Because Stacks are LIFO, pushing the Left child *last* ensures it is popped out and explored *first*, satisfying the Left-plunging nature of Preorder DFS!).

Python Code:

def iterative_dfs_preorder(root):
    if root is None:
        return
    
    stack = [root] # Initialize manual stack
    
    while len(stack) > 0:
        node = stack.pop() # Pop the top node
        print(node.val, end=" ")
        
        # Push RIGHT child first!
        if node.right is not None:
            stack.append(node.right)
            
        # Push LEFT child second!
        if node.left is not None:
            stack.append(node.left)

6. Tracing the Iterative Execution #

1. 1. Push A. Stack: [A].

1. 2. Pop A. Print A.

1. 3. Push Right C, Push Left B. Stack: [C, B].

1. 4. Loop restarts. Pop top plate (B). Print B.

1. 5. (If B had children, they would be pushed here).

1. 6. Loop restarts. Pop top plate (C). Print C.

7. Complexity Analysis #

• Time Complexity: $O(N)$. The algorithm mechanically pops every single node off the stack exactly once.

• Space Complexity: $O(H)$ for Recursion (OS Stack frame height), or $O(W)$ for Iterative (Width of the tree stored in the manual stack). In worst-case scenarios, Space is $O(N)$.

8. Common Mistakes #

• Pushing Left then Right in Iterative DFS: If you manually push the Left child into the Stack first, and the Right child second, the LIFO rules mean the Right child is extracted first! Your algorithm will accidentally execute a mirror-image "Right-leaning" DFS. Always push the Right child first!

9. Exercises #

1. 1. Write a Java or C++ implementation of the Iterative Preorder DFS.

1. 2. Theoretically explain what physical mechanism causes a StackOverflowError during a deep recursive DFS traversal.

10. MCQs with Answers #

11. Interview Preparation #

• *Algorithmic Conversion:* "The codebase has a recursive DFS function that is causing StackOverflowError exceptions in production on deep database trees. Whiteboard the exact Iterative conversion logic to fix the server." *(Answer: Deploy a while loop and a manual Stack data structure! Push root, loop while stack not empty, pop, process, push right, push left!)*

12. Summary #

13. Next Chapter Recommendation #