Introduction

Previously I wrote a post about the recusive traversal of binary tree:

Binary Tree Traversal: A Deep Dive into Recursion
Master binary tree traversal in Python with a systematic approach to recursion. Learn the three essential elements for writing reliable recursive algorithms and implement preorder, inorder, and postorder traversals. Perfect for programmers looking to strengthen their tree manipulation skills.
Fanyang Meng's BlogFanyang Meng

Why should we consider using iterative methods (non-recursive approaches) for traversing binary trees? The answer lies in understanding how recursion works behind the scenes.

When we use recursion, each recursive call pushes local variables, parameter values, and return addresses onto the call stack. As the recursion unwinds, these values are popped from the stack top, allowing the program to return to previous positions in the execution flow. Understanding this mechanism reveals why we can use an explicit stack to implement binary tree traversals iteratively.

Pre-order Traversal (Iterative Approach)

Let's start with pre-order traversal.

Pre-order traversal follows the pattern: root-left-right. Since we process the root node first, we can start by pushing it onto our stack. Then, we'll push the right child followed by the left child.

Why push the right child before the left? Because when we pop from the stack, we want to process nodes in root-left-right order, and stacks follow Last-In-First-Out (LIFO) behavior.

Step 5: Continue until stack empty
Stack: []
Result: [1,2,4,5,3]
Step 4: Pop 4, process it
Stack: [3,5]
Result: [1,2,4]
4 popped and processed
no children to push
Step 3: Pop 2, push its right then left
Stack: [3,5,4]
Result: [1,2]
2 popped and processed
right child (5) pushed first
left child (4) pushed last
Step 2: Pop 1, push right then left
Stack: [3,2]
Result: [1]
1 popped and processed
right child (3) pushed first
left child (2) pushed last
Step 1: Push root
Stack: [1]
Result: []
Tree
1
2
3
4
5

Here's the Python implementation (note that we don't push None nodes onto the stack):

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            # Process root node first
            result.append(node.val)
            # Push right child first (will be processed later)
            if node.right:
                stack.append(node.right)
            # Push left child last (will be processed sooner)
            if node.left:
                stack.append(node.left)
                
        return result
python

While this implementation might seem straightforward, you might wonder: "Can we modify this code slightly to implement in-order traversal?"

Actually, we can't! The reason becomes clear when we look at in-order traversal.

In-order Traversal (Iterative Approach)

To understand why the pre-order approach doesn't work for in-order traversal, we need to distinguish between two operations:

  1. Processing: Adding elements to our result list
  2. Visiting: Traversing through nodes

In pre-order traversal, we visit and process nodes in the same order (root-left-right), which allows for a simpler implementation. However, in-order traversal (left-root-right) requires us to visit nodes in one order but process them in another.

Final Step
Stack: []
Current: null
Result: [4,2,5,1,3]
Process 3,
traversal complete
Step 5: Process root
Stack: []
Current: right of 1 (3)
Result: [4,2,5,1]
Pop 1, add to result,
move to its right
Step 4: Handle right child
Stack: [1]
Current: null
Result: [4,2,5]
Process 5, 
no right child
Step 3: Process parent
Stack: [1]
Current: right of 2 (5)
Result: [4,2]
Pop 2, add to result,
move to its right
Step 2: Process leftmost
Stack: [1,2]
Current: right of 4 (null)
Result: [4]
Pop 4, add to result,
move to its right
Step 1: Push left path from root
Stack: [1,2,4]
Current: null
Result: []
Pushed 1,2,4 while following left path
Tree
1
2
3
4
5

For in-order traversal, we need to visit nodes from top to bottom until we reach the leftmost leaf, but we can't process them until we've finished exploring the left subtree. This mismatch between visiting and processing order requires a different approach using a pointer to track our current position:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        stack = []
        result = []
        current = root
        
        while current or stack:
            # Traverse to leftmost node
            while current:
                stack.append(current)
                current = current.left
            
            # Process current node and move to right subtree
            current = stack.pop()
            result.append(current.val)
            current = current.right
            
        return result
python

Post-order Traversal (Iterative Approach)

Post-order traversal follows the left-right-root pattern. Here's a clever approach: if we modify our pre-order traversal to follow a root-right-left pattern and then reverse the result, we'll get the left-right-root order we want!

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            # Push left child first (will be processed later)
            if node.left:
                stack.append(node.left)
            # Push right child last (will be processed sooner)
            if node.right:
                stack.append(node.right)
                
        # Reverse to get left-right-root order
        return result[::-1]
python

Workflow:

Step 6: Final node and reverse
Stack: []
Initial: [1,3,2,5,4]
Final: [4,5,2,3,1]
Pop 4, add to result
Reverse array to get
post-order traversal
Step 5: Process remaining nodes
Stack: [4]
Result: [1,3,2,5]
Pop 5, add to result
No children to push
Step 4: Pop 2, add to result, push children
Stack: [4,5]
Result: [1,3,2]
Pop 2, add to result
Push left(4) first
Push right(5) last
Step 3: Pop 3, add to result
Stack: [2]
Result: [1,3]
Pop 3, add to result
No children to push
Step 2: Pop 1, add to result, push left & right
Stack: [2,3]
Result: [1]
Pop 1, add to result
Push left(2) first
Push right(3) last
Step 1: Push root
Stack: [1]
Result: []
Initial state
Tree
1
2
3
4
5

Conclusion

We've now implemented all three traversal methods iteratively, and you might notice that pre-order and in-order implementations look quite different. This contrasts with recursive implementations, where the code structures are very similar.

The key insight is that pre-order traversal allows simultaneous visiting and processing of nodes, while in-order traversal requires us to handle these operations separately. This fundamental difference leads to distinct implementation approaches.

In practice, while recursive implementations are often more intuitive, understanding these iterative approaches provides valuable insights into tree traversal algorithms and can be useful in scenarios where stack space is a concern or when explicit stack control is needed.

A natural follow-up question might be: "Is it possible to implement all three traversal methods using a unified iterative approach?" Indeed it is, but that's a topic for another discussion, as it involves a more complex but more general algorithm that works for all three traversal orders.