Unified Approach to Binary Tree Iterative Traversal

Binary tree traversal is a fundamental concept in computer science, and while recursive solutions are intuitive, iterative approaches can be more efficient in practice. This blog post introduces a unified iterative method for implementing all three traversal orders (inorder, preorder, and postorder) using Python.

Background

In our previous discussions, we explored two main approaches to binary tree traversal. First, we learned about recursive traversal methods, which elegantly capture the natural structure of tree operations. The recursive approach is beautifully simple - once you implement one traversal order, adapting it to other orders only requires rearranging a few lines of code.

Then we ventured into iterative traversal using stacks, eliminating the recursive call stack. However, this is where we encountered an interesting challenge: the iterative implementations didn't share the same elegant uniformity as their recursive counterparts.

The Challenge with Traditional Iterative Approaches

The traditional iterative implementations have a notable inconsistency. While preorder and postorder traversals share some similarities in their stack-based approach, the inorder traversal feels like a completely different algorithm. Sometimes we're manipulating the stack directly, other times we're using pointer-based traversal. This lack of uniformity creates several problems:

It makes the code harder to memorize and understand
Each traversal order requires learning a new mental model
Implementing all three traversals requires maintaining three distinct approaches

The Key Insight: Node Visitation vs Processing

The core challenge lies in managing two distinct operations that happen at different times:

Node Visitation: When we first encounter a node and need to decide how to handle its children
Node Processing: When we actually want to add the node's value to our result

In recursive implementations, these operations naturally align with the recursive call stack. However, in iterative implementations, we need an explicit way to distinguish between these two phases.

Foundational Concepts

Before diving into the implementations, let's recall the three traversal orders:

Preorder: Center → Left → Right
Inorder: Left → Center → Right
Postorder: Left → Right → Center

The Solution: A Unified Marking Approach

We can achieve a unified approach by explicitly marking nodes to indicate their processing state. There are two elegant ways to implement this marking:

Null Marker Method (Space-Efficient)
- When we visit a node, we push it onto the stack
- We immediately follow it with a None (null) marker
- When we encounter the None marker while popping from the stack, we know the next node is ready for processing
Boolean Flag Method (More Intuitive)
- We store each node in the stack along with a boolean flag
- False (default) means "first visit - need to handle children"
- True means "second visit - ready for processing"
- This approach is particularly interview-friendly due to its clarity

Both methods allow us to maintain the same structural approach across all three traversal orders, differing only in the sequence in which we push nodes onto the stack. This creates the unified pattern we've been seeking, making the code more maintainable and easier to understand.

Let's examine both approaches in detail, starting with the inorder traversal.

Inorder Traversal

Here's the implementation using the null marker method:

class BinaryTreeSolution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        if root:
            stack.append(root)
            
        while stack:
            node = stack.pop()
            if node is not None:
                # Process right-center-left for stack (becomes left-center-right when popped)
                if node.right:
                    stack.append(node.right)  # Right child first
                    
                stack.append(node)            # Center node
                stack.append(None)            # Marker for processing
                
                if node.left:
                    stack.append(node.left)   # Left child last
            else:
                # When we find a marker, process the next node
                node = stack.pop()
                result.append(node.val)
                
        return result

And here's the same traversal using the boolean flag method:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [(root, False)] if root else []
        
        while stack:
            node, visited = stack.pop()
            
            if visited:
                result.append(node.val)
                continue
                
            # Arrange nodes in reverse order of desired traversal
            if node.right:
                stack.append((node.right, False))
            stack.append((node, True))
            if node.left:
                stack.append((node.left, False))
                
        return result

Preorder Traversal

None marker Approach:

class BinaryTreeSolution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
      result = []
      stack = []
      if root:
          stack.append(root)
          
      while stack:
          node = stack.pop()
          if node is not None:
              # Process in reverse order of desired traversal
              if node.right:    # Right pushed first (processed last)
                  stack.append(node.right)
              if node.left:     # Left pushed second (processed second)
                  stack.append(node.left)
              stack.append(node)  # Node pushed last (processed first)
              stack.append(None)  # Marker to indicate processing
          else:
              # Process the node when we hit its marker
              node = stack.pop()
              result.append(node.val)
      
      return result

Compare it with inorder one, we can find only the order has changed, the logic remains the same.

Boolean Flag Approach:

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
      result = []
      # Each stack element is a tuple: (node, visited_flag)
      stack = [(root, False)] if root else []
      
      while stack:
          node, visited = stack.pop()
          
          if visited:  # If we've seen this node before, process it
              result.append(node.val)
              continue
              
          # Add nodes in reverse order of desired traversal
          if node.right:
              stack.append((node.right, False))
          if node.left:
              stack.append((node.left, False))
          # Preorder: process center first
          stack.append((node, True))
      
      return result

Postorder Traversal

None marker Approach:

class BinaryTreeSolution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
      result = []
      stack = []
      if root:
          stack.append(root)
          
      while stack:
          node = stack.pop()
          if node is not None:
              # Process in reverse order of desired traversal
              stack.append(node)  # Node pushed first (processed last)
              stack.append(None)  # Marker for processing
              if node.right:    # Right pushed second (processed second)
                  stack.append(node.right)
              if node.left:     # Left pushed last (processed first)
                  stack.append(node.left)
          else:
              node = stack.pop()
              result.append(node.val)
      
      return result

Boolean Flag Approach:

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
      result = []
      stack = [(root, False)] if root else []
      
      while stack:
          node, visited = stack.pop()
          
          if visited:  # If we've seen this node before, process it
              result.append(node.val)
              continue
              
          # Add nodes in reverse order of desired traversal
          # Postorder: process center last
          stack.append((node, True))
          if node.right:
              stack.append((node.right, False))
          if node.left:
              stack.append((node.left, False))
      
      return result

Key Points to Understand

Stack Order vs Processing Order
- Due to the stack's LIFO (Last In, First Out) nature, nodes are processed in reverse order of how they're pushed
- If we want to process A before B, we need to push B before A
The Role of None Markers
- A None marker tells us "process the next node" when we encounter it
- It helps distinguish between "visiting" a node and "processing" it
Order Comparison For the same node, the push order differs:
- Preorder: [right, left, center, None]
- Inorder: [right, center, None, left]
- Postorder: [center, None, right, left]

The main difference between the traversal types is just the order in which we push the nodes (center/left/right) onto the stack. This unified approach makes it easier to understand and implement all three traversal types using the same basic pattern.

Advantages and Trade-offs

The unified approach offers several benefits:

Consistent pattern across all traversal types
Easier to maintain and modify
More straightforward to debug

However, it does come with some trade-offs:

Slightly more complex than specialized implementations
Uses more memory due to markers/flags
May be slower than optimized specific implementations

Conclusion

While this unified approach might not be the most efficient solution for every situation, it provides a consistent mental model for understanding and implementing binary tree traversals. For interviews or situations where code maintainability is prioritized over maximum performance, this approach can be particularly valuable.

Whether you choose to use the null marker method or the boolean flag method depends on your specific needs:

The null marker method is more memory-efficient but might be less intuitive
The boolean flag method is more explicit and easier to understand but uses slightly more memory

Choose the approach that best fits your needs and coding style, and remember that understanding both methods will make you a more versatile programmer.