We need to traverse a binary tree in postorder, which means: visit the left subtree first, then the right subtree, then the current node. This is the opposite of preorder (root, left, right) and different from inorder (left, root, right).

Postorder traversal has a natural recursive definition, which makes the recursive solution almost trivial. But the real challenge, and the reason interviewers ask this problem, is implementing it iteratively. Unlike preorder and inorder, postorder is the trickiest of the three traversals to do without recursion. The difficulty comes from the fact that we need to visit the root last, but we encounter it first as we descend the tree. We need to somehow "remember" to come back to a node after both its subtrees have been processed.

The key observation is that postorder (left, right, root) is the reverse of a modified preorder (root, right, left). This insight unlocks an elegant iterative solution.

Key Constraints:

Intuition

Postorder traversal is defined recursively: visit the left subtree, visit the right subtree, then visit the root. So the recursive solution writes itself. You just follow the definition: recurse left, recurse right, add the current node's value to the result.

This is the solution most people write first, and it's perfectly correct. The recursion handles the "come back to the root after both subtrees" problem automatically through the call stack. When the left recursive call returns, the right one starts. When the right one returns, we add the current node. The call stack is doing all the bookkeeping for us.

Algorithm

Example Walkthrough

Code

The recursive solution is correct and optimal in time, but it relies on the call stack. For very deep trees, this could cause a stack overflow.

Can we eliminate the recursion and manage the stack ourselves?

Intuition

Here's the clever observation that makes iterative postorder much easier than it first appears. Consider what happens if you do a modified preorder traversal where you visit the root, then the right child, then the left child. That gives you: root, right, left. Now reverse that result, and you get: left, right, root. That's postorder.

So instead of wrestling with the tricky question of "when is it safe to pop a node," we can sidestep the problem entirely. Do a modified preorder (which is straightforward with a stack), then reverse the output.

Algorithm

We push left before right. Since a stack is LIFO, the right child gets popped first. This gives us root-right-left traversal order. Reversing produces left-right-root, which is postorder.

Example Walkthrough

Code

This approach works well, but we're not doing a "true" postorder traversal. We collect everything and reverse at the end.

Can we visit nodes in genuine postorder using a stack, without any reversal?

Intuition

This approach truly mimics what the recursion does, without the reversal trick. The challenge is clear: when we're at a node, we need to process its left subtree, then its right subtree, and only then process the node itself. With a stack, we naturally encounter the node before its children. So we need a way to "skip" processing a node until both its children are done.

The trick is to track the previously processed node. When we look at the top of the stack, we ask: have we already processed this node's right child? If the right child is null or equals the previously processed node, we know the right subtree is done, so it's safe to process the current node. Otherwise, we need to go right first.

Algorithm

Example Walkthrough

Code