Iterative Postorder Traversal with a Stack

Welcome back. In our previous lessons, we successfully adapted a unified iterative DFS template to handle both preorder (Root -> Left -> Right) and inorder (Left -> Root -> Right) traversals. The key was manipulating when we "visit" a node relative to pushing it onto and popping it from the stack.

Today, we tackle the final and most intricate of the classic traversals: iterative postorder traversal. Your goal is to implement the Left -> Right -> Root sequence using an explicit stack. This pattern is less straightforward because you must delay visiting a node until you have fully explored both of its children. This requirement makes it a common and challenging interview question. We will explore two primary, effective patterns to solve this problem neatly.

The Challenge of Postorder

With preorder, we visit a node immediately. With inorder, we visit after the left subtree is done. With postorder, we must visit after both the left and right subtrees are done. Using our simple currentNode and stack template, it's not immediately obvious how the algorithm can know if it's returning to a parent node from the left child (and should now go right) or from the right child (and should now visit the parent).

Let's look at a couple of standard patterns to solve this.

Method 1: The Intuitive Two-Stack Approach

Perhaps the most direct way to reason about iterative postorder is to work backward.

• The postorder sequence is Left -> Right -> Root.
• If we reverse this sequence, we get Root -> Right -> Left.

This reversed sequence looks remarkably similar to a preorder traversal (Root -> Left -> Right), with the only difference being that we traverse the right child before the left child. We can easily implement this modified preorder traversal. The full algorithm then becomes:

1. Create two stacks, let's call them stack1 and stack2.
2. Push the root node onto stack1.
3. While stack1 is not empty:
   • Pop a node from stack1.
   • Push that node onto stack2.
   • If the popped node has a left child, push the left child onto stack1.
   • If the popped node has a right child, push the right child onto stack1. (Notice we push left then right, so that right is processed first from the LIFO stack).
4. Once the loop finishes, stack2 holds the nodes in the correct postorder sequence. Pop all elements from stack2 and add them to your result list.

This method is elegant because it reuses a familiar pattern (preorder) with a simple twist. The 'take U forward' channel provides an excellent visual demonstration of this logic.

The image below, from the 'takeuforward' website, captures a moment in this process, showing how a node popped from stack1 is pushed to stack2, and its children are then pushed to stack1.

While this two-stack approach is correct and easy to understand, it uses O(N) auxiliary space for the second stack, in addition to the O(H) space for the first. A common follow-up is to solve it using only one stack.

Method 2: The One-Stack Approach

To use a single stack, we need a mechanism to determine if a node's right subtree has been visited. The most robust way to do this is by keeping track of the last node that was processed. This approach perfectly simulates the behavior of the recursive call stack.

The algorithm is a more sophisticated version of our general iterative template:

1. Initialize an empty stack and a currentNode pointer set to the root.
2. Initialize a lastVisitedNode pointer to null.
3. Loop as long as currentNode is not null or the stack is not empty.
4. Go left: If currentNode is not null, push it onto the stack and move left: currentNode = currentNode.left.
5. Check right or visit: If currentNode is null:
   • peek at the node on top of the stack (peekNode).
   • Case 1 (Go Right): If peekNode has a right child and that right child has not been visited yet (peekNode.right != lastVisitedNode), it's time to explore the right subtree. Set currentNode = peekNode.right and continue the loop.
   • Case 2 (Visit Node): Otherwise (if peekNode has no right child, or its right child has already been visited), we can finally process peekNode. Add its value to the result, pop it from the stack, update lastVisitedNode = peekNode, and crucially, set currentNode = null to ensure we continue processing from the stack in the next iteration.

This logic is more complex, but it's a powerful pattern. The Tushar Roy video provides one of the clearest explanations available for this specific algorithm.

For a textual reference and another perspective on single-stack solutions, the GeeksforGeeks article is very thorough. The method we just discussed corresponds to their third approach.

An Alternative One-Stack Trick

There is another clever one-stack method that relates back to our first approach. It generates the Root -> Right -> Left sequence and then reverses the result list at the very end.

Complexity Analysis

For all the methods discussed, the complexity is the same:

• Time Complexity: $O(N)$, as each node is visited and processed a constant number of times.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This represents the maximum depth of the stack. For a balanced tree, this is $O(\log N)$, and for a skewed tree, it's $O(N)$. Even the two-stack method's space is dominated by stack2 which holds N elements in the end, but the concurrent stack usage is what matters, which is O(H) + O(N), simplifying to O(N). The one-stack methods are strictly O(H).

Conclusion

You've now completed the trifecta of iterative tree traversals. Postorder is the most complex, but mastering it gives you a robust toolkit for a wide range of tree problems.

Key Takeaways:

• Postorder traversal follows the Left -> Right -> Root sequence.
• Two-Stack Method: An intuitive approach that computes a modified preorder traversal (Root -> Right -> Left) and uses a second stack to reverse the sequence into postorder.
• One-Stack Method: A more space-efficient but complex approach that requires tracking the lastVisitedNode to decide whether to ascend from the right subtree or descend into it.
• Reversal Trick: A clever one-stack pattern that generates a Root -> Right -> Left sequence and reverses the final list.

In the next lesson, we will step back and compare the iterative approaches you've learned with their recursive counterparts, discussing the trade-offs in terms of space complexity, stack overflow risk, and implementation clarity.