Iterative Postorder with Stack
You'll learn: How to perform postorder traversal (left-right-root) iteratively using a stack, which is trickier than iterative preorder or inorder because you must ensure both children are processed before the root.
Why Postorder Is Harder Iteratively
Postorder traversal visits nodes in left-right-root order. Unlike preorder or inorder, when you pop a node from the stack, you can't immediately process it—you must first ensure both its left and right children have been visited. This requires tracking which nodes you've already handled.
Two Common Approaches
1. Two-Stack Method
The simplest approach uses two stacks:
- Use a modified preorder (root-right-left) and push results to a second stack
- When done, the second stack contains nodes in postorder (left-right-root)
Analogy: It's like reading a book backwards—you flip the pages in reverse order to get the opposite sequence.
2. Single Stack with Tracking
Use one stack but track the last visited node:
- Push a node and go left as far as possible
- When you can't go left, check if there's a right child and it hasn't been visited
- If the right child exists and is unvisited, process it
- Otherwise, pop and process the current node
This approach requires a lastVisited variable to remember which node you just processed, preventing infinite loops.
The Core Challenge
The difficulty is ensuring you don't process a parent until after returning from both subtrees. You need explicit tracking because, unlike recursion (which uses the call stack's implicit state), iteration requires you to manually remember where you've been.
Key Takeaway: Iterative postorder requires either two stacks (simpler logic) or one stack with explicit tracking of the last visited node to maintain left-right-root order without recursion's implicit state management.