Iterative Inorder Traversal with a Stack

1. From Recursive Magic to Iterative Logic

Recall the three steps of a recursive inorder traversal:

1. Recursively traverse the left subtree.
2. Visit the root node.
3. Recursively traverse the right subtree.

The "magic" of recursion is that the programming language manages a call stack behind the scenes to remember where to return after each function call. When we go from root to root.left, the call stack remembers the root node so we can come back to it later.

Our goal with an iterative solution is to replace this implicit call stack with an explicit stack data structure that we control. We will use a simple Python list as our stack. This stack will store the nodes we need to visit later, perfectly mimicking the "pause and resume" nature of recursion.

2. The Core Algorithm: Simulating Recursion with a Stack

The logic of iterative inorder traversal hinges on a simple process that we repeat until all nodes are visited.

The algorithm works as follows:

1. Start with the root as your current node and an empty stack.
2. Go as far left as possible: As long as the current node is not None, push it onto the stack and move to its left child (current = current.left). This saves the path of nodes we need to revisit.
3. Visit and go right: When current becomes None, it means we've hit the end of a leftward path. Now, it's time to process a node.
   • Pop a node from the stack. This is the node we'll "visit" (e.g., add its value to our result list).
   • After visiting, set the current pointer to the popped node's right child.
4. Repeat: Go back to step 2 with the new current node. The entire process continues as long as there are nodes to process (i.e., current is not None or the stack is not empty).

This can be tricky to grasp just from text. The following video gives an excellent conceptual walkthrough, simulating both the recursive call stack and the manual iterative stack.

3. Step-by-Step Implementation in Python

Now that you have the conceptual foundation, let's look at how this translates into Python code. The logic directly follows the steps we just outlined.

The following resource provides a clean implementation and a breakdown of the algorithm.

Here is the code, which you should now be able to recognize:

# Assume this TreeNode class is defined
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal_iterative(root: TreeNode):
    result = []
    stack = []
    current = root
    
    # The loop continues as long as there's something to process
    while current is not None or stack:
        
        # 1. Go as far left as possible, pushing nodes onto the stack
        while current is not None:
            stack.append(current)
            current = current.left
        
        # At this point, current is None. We need to process a node from the stack.
        # 2. Pop the last node we saved
        current = stack.pop()
        
        # 3. "Visit" the node by adding its value to the result
        result.append(current.val)
        
        # 4. Now, try to explore the right subtree of the node we just visited
        current = current.right
        
    return result

To see this code being built and explained live, you can watch the final part of the NeetCode video.

      F
     / \
    B   G
   / \   \
  A   D   I
     / \ /
    C  E H 

4. Complexity Analysis

A key reason to learn different algorithm variations in competitive programming is to understand their performance trade-offs.

• Time Complexity: $O(N)$
  Each node in the tree is pushed onto the stack exactly once and popped exactly once. Therefore, we visit each node a constant number of times, making the time complexity linear with respect to the number of nodes, $N$.

• Space Complexity: $O(H)$
  The space required is determined by the maximum number of elements in our stack at any one time. This occurs when we traverse the longest path from the root down to a leaf. In the worst case (a completely skewed tree, like a linked list), all $N$ nodes might be on the stack. In the best case (a perfectly balanced tree), the height $H$ is about $\log N$.

  • Worst Case: $O(N)$
  • Average/Best Case: $O(\log N)$

Notice that the space complexity is identical to the recursive solution. The primary advantage of the iterative method is not a reduction in theoretical worst-case space but the avoidance of the system's hard recursion depth limit, making it more robust for very deep trees.

Conclusion

Congratulations! You've now implemented one of the most fundamental tree algorithms both recursively and iteratively. Understanding how to manually manage a stack to simulate recursion is a skill that will be invaluable for many other problems in competitive programming.

Key Takeaways:

• Iterative inorder traversal uses an explicit stack to replicate the behavior of the recursive call stack.
• The core logic is a loop that repeatedly:
  1. Travels to the leftmost node, pushing parent nodes onto the stack.
  2. Pops a node, "visits" it, and then moves to its right child.
• This process continues until both the current pointer is null and the stack is empty.
• The time complexity is $O(N)$ and the space complexity is $O(H)$, where $H$ is the tree's height.

Up Next:
We have thoroughly explored tree traversals using a depth-first approach (going deep before going wide), using both recursion and a stack. In our next lesson, we will shift gears to a different traversal strategy: level-order traversal. This is a breadth-first approach that explores the tree level by level, and it uses a queue instead of a stack.