Iterative Tree Traversal with Stacks

1. From Recursion to Iteration: The Role of the Stack

The transition from a recursive to an iterative solution involves replacing the implicit function call stack with an explicit stack data structure that you manage yourself. The core idea remains the same: we need a way to "remember" which nodes to visit later.

• In pre-order (Root -> Left -> Right), we process a node and then need to remember to visit its children, left first, then right.
• In in-order (Left -> Root -> Right), we can't process a node until its entire left subtree has been visited. The stack helps us keep track of the path of "parent" nodes as we descend to the leftmost leaf.

Let's explore the pattern for each traversal.

2. Iterative Pre-order Traversal (Root -> Left -> Right)

The iterative pre-order traversal has a very direct and intuitive implementation using a stack. Since a stack is a Last-In, First-Out (LIFO) data structure, we can leverage this property to ensure we process the left child before the right child.

The algorithm is as follows:

1. Initialize an empty list for the results and an empty stack.
2. If the root is null, return the empty list. Otherwise, push the root node onto the stack.
3. Loop as long as the stack is not empty:
   a. Pop a node from the stack. Let's call it current.
   b. Add current.val to the results list.
   c. Push the right child first, if it exists.
   d. Push the left child second, if it exists.

By pushing the right child before the left child, the LIFO nature of the stack guarantees that the left child will be on top, ready to be popped and processed in the next iteration.

The following resource provides an excellent and concise explanation of this algorithm, along with code implementations in C++, Java, Python, and JavaScript.

Here's a summary of the Python code you just reviewed, which perfectly implements this pattern:

def preorderTraversal(root):
    if not root:
        return []

    stack = [root]
    result = []

    while stack:
        node = stack.pop()
        result.append(node.val) # 1. Process node

        if node.right:
            stack.append(node.right) # 2. Push right child
        
        if node.left:
            stack.append(node.left) # 3. Push left child

    return result

This image provides a helpful visual trace of the process:

3. Iterative In-order Traversal (Left -> Root -> Right)

The iterative in-order traversal requires a slightly more complex pattern because we cannot process a node until we have finished its entire left subtree. This means we must first travel all the way down to the leftmost node.

The algorithm for this is a two-phase loop:

1. Initialize an empty list for the results, an empty stack, and a current pointer set to the root.
2. Loop as long as current is not None OR the stack is not empty:
   a. Phase 1: Go Left. While current is not None, push it onto the stack and move to its left child (current = current.left). This loop continues until we find a None left child, loading up the stack with the path we took.
   b. Phase 2: Process and Go Right. Once current is None, it means we've hit the end of a leftward path. Now we pop a node from the stack.
   i. This popped node is the next one to be processed in the in-order sequence. Add its value to the results.
   ii. Set current to the popped node's right child (current = node.right). The main loop will then begin again from Phase 1 for this new current node.

This video from NeetCode provides an outstanding conceptual walkthrough and coding demonstration of this exact pattern.

This image also gives a great step-by-step trace of the process, showing how the stack and the current node interact.

The resulting Python code looks like this:

def inorderTraversal(root):
    stack = []
    result = []
    curr = root

    while curr or stack:
        # Phase 1: Go left and push nodes onto the stack
        while curr:
            stack.append(curr)
            curr = curr.left
        
        # Phase 2: Pop, process the node, and go right
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
        
    return result

      10
     /  \
    5    15
   / \    \
  2   7    20

Conclusion

Excellent work! You have now learned how to implement pre-order and in-order traversals both recursively and iteratively. Understanding both approaches is a sign of a well-rounded developer and is frequently tested in interviews.

Key Takeaways:

• Iterative traversals replace the implicit call stack of recursion with an explicit stack data structure.
• Iterative Pre-order has a simple pattern: Pop a node, process it, then push its right child followed by its left child onto the stack.
• Iterative In-order uses a two-phase approach: first, traverse as far left as possible while pushing nodes onto the stack; then, pop a node, process it, and move to its right child to repeat the process.
• For both traversals, the time complexity is O(N) and the space complexity is O(H) (the height of the tree), which is the same as their recursive counterparts.

In our next lesson, we will use these traversal techniques as building blocks to solve common tree problems, such as finding a tree's maximum depth, its diameter, and checking if it's balanced.