Binary Tree Postorder Traversal: The Two-Stacks Trick
Iterative binary tree postorder traversal with two stacks, explained step by step — intuition, JavaScript code, a traced walkthrough, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Postorder traversal visits a tree in left, right, root order — children before the parent, always. The recursion is trivial. The iterative version is where interviewers watch you sweat, because the root has to come last, and a plain stack naturally wants to emit the node it's holding first.
There is an inorder-style one-stack solution that carefully tracks which node it last visited, and it's fiddly. The two-stacks approach sidesteps all of that. You build a slightly wrong order that's trivial to produce, then reverse it into the right one. Two stacks, no bookkeeping, no edge cases.
The problem
Given the root of a binary tree, return its node values in postorder: for every node, list its left subtree, then its right subtree, then the node itself. An empty tree returns [], and values can repeat, so the traversal must follow node references, not values.
1
/ \
2 3
Output: [2, 3, 1]Node 1 comes last because a parent is only emitted after both of its subtrees are done. Leaf 2 (left) precedes leaf 3 (right), and the root closes the sequence.
The recursive baseline
The textbook definition maps straight onto code:
function postorder(root, ans = []) {
if (!root) return ans;
postorder(root.left, ans);
postorder(root.right, ans);
ans.push(root.val);
return ans;
}This is correct and O(n), but it leans on the language call stack to remember "I still owe you this node after its children finish." On a pathological, deeply skewed tree of n nodes, that hidden stack is n frames deep and can overflow. Interviewers ask for the iterative version precisely to see you make that implicit stack explicit — and to expose whether you understand why postorder is the awkward one to unroll.
The key insight: build the reverse, then flip it
Look at postorder — left, right, root — and read it backwards: root, right, left. That reversed order is almost preorder. Standard preorder is root, left, right; this is just preorder with the two children swapped. And a root-first order is exactly what a single stack produces effortlessly: pop a node, record it, push its children.
So the plan splits into two phases:
- Phase 1 — run a modified preorder that visits root, right, left, but instead of writing results out, push each visited node onto a second stack. Because a stack reverses whatever you push into it,
stack2ends up holding the nodes in root-right-left fill order. - Phase 2 — pop
stack2from top to bottom. Popping reverses root-right-left into left-right-root, which is postorder.
stack1 is the driver that runs the traversal. stack2 is a collector whose only job is to reverse. To get root-right-left out of stack1, you push the left child first, then the right child, so the right child sits on top and is popped first.
The optimal solution
This is exactly the algorithm the Two Stacks visualizer steps through:
function postorderTraversal(root) {
if (!root) return [];
const stack1 = [root];
const stack2 = [];
while (stack1.length) {
const node = stack1.pop();
stack2.push(node);
if (node.left) stack1.push(node.left);
if (node.right) stack1.push(node.right);
}
const result = [];
while (stack2.length) {
result.push(stack2.pop().val);
}
return result;
}Two loops, no visited set, no "last visited node" pointer. The first loop drains stack1 into stack2; the second drains stack2 into result. Push left before right in loop one — flip that and you get right-left-root, which reverses to the mirror image, not postorder.
Walkthrough
Tracing root = [1, 2, 3] — the balanced tree above, expected output [2, 3, 1]. Stacks are written bottom → top, so the rightmost value is what pops next.
| Step | Action | node | stack1 | stack2 | result |
|---|---|---|---|---|---|
| 1 | init: push root | — | [1] | [] | [] |
| 2 | pop 1 → push to S2 | 1 | [] | [1] | [] |
| 3 | push left 2, push right 3 | 1 | [2, 3] | [1] | [] |
| 4 | pop 3 → push to S2 (no kids) | 3 | [2] | [1, 3] | [] |
| 5 | pop 2 → push to S2 (no kids) | 2 | [] | [1, 3, 2] | [] |
| 6 | S1 empty → Phase 2 begins | — | [] | [1, 3, 2] | [] |
| 7 | pop 2 from S2 | 2 | [] | [1, 3] | [2] |
| 8 | pop 3 from S2 | 3 | [] | [1] | [2, 3] |
| 9 | pop 1 from S2 | 1 | [] | [] | [2, 3, 1] |
Watch step 3: pushing left (2) then right (3) leaves 3 on top of stack1, so it's popped next — that's the root-right-left order forming. By the end of Phase 1, stack2 reads [1, 3, 2] bottom-to-top, which is root-right-left. Phase 2 pops it top-first and lands on [2, 3, 1] — postorder, exactly as promised.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Each node is pushed and popped from stack1 once and from stack2 once — four constant-time touches per node. |
| Space | O(n) | Both stacks together hold at most n node references, and result is n values. |
Compared with the recursive baseline, time is identical; the win is that the O(n) stack space is now an explicit heap-allocated array instead of the call stack, so a deep tree can't blow the stack. The trade-off versus a one-stack iterative postorder is honest: two stacks use more auxiliary memory, but you buy total simplicity — no last-visited tracking, no ambiguous "should I go down or emit?" branch.
Common mistakes
- Pushing right before left in Phase 1. That produces right-left-root in
stack2, which reverses to the mirror traversal, not postorder. Left-first is the whole trick. - Forgetting to reverse. If you read
stack2bottom-to-top (or push its nodes straight intoresultin fill order) you get root-right-left — a valid traversal, just not the one asked for. The second stack exists only to reverse. - Trying to emit into
resultduring Phase 1. There's no correct moment to emit a node in the first loop — a parent is seen before its children finish. Emitting must wait for Phase 2. - Skipping the empty-tree guard. Without
if (!root) return [], you pushnullontostack1, then dereferencenode.lefton it and crash. - Confusing this with preorder. Two-stacks postorder is a modified preorder internally, which trips people into thinking the output is preorder. The reversal is what converts it.
Where this pattern shows up next
The "build a reversible order with one stack, flip it" idea and the broader iterative-traversal toolkit carry across the whole family:
- Binary Tree Preorder Traversal — the recursive root-left-right baseline this trick quietly reuses.
- Binary Tree Preorder Traversal - Iterative — the single-stack, push-right-before-left engine that Phase 1 mirrors.
- Binary Tree Inorder Traversal — the recursive left-root-right ordering, the third member of the DFS trio.
- Binary Tree Inorder Traversal - Iterative — the go-left-then-emit stack pattern, the one iterative traversal that genuinely needs different machinery.
You can also step through the two-stacks traversal interactively and watch stack2 fill in reverse-postorder before Phase 2 flips it.
FAQ
Why does postorder traversal need two stacks when preorder needs only one?
Preorder emits the root first, which is exactly what a single stack gives you: pop a node, record it, push its children. Postorder needs the root last, and a stack can't naturally hold a node back until both subtrees finish without extra bookkeeping. The two-stacks method dodges that by producing the easy reverse order (root-right-left) in the first stack, then using the second stack purely to reverse it into left-right-root. The reversal replaces the tricky "wait for children" logic.
How is the two-stacks postorder different from the one-stack version?
Both are O(n) time and O(n) space, but they trade complexity for memory differently. The one-stack version keeps a single stack and a "last visited node" pointer, deciding at each step whether to descend further or emit the current node — correct but fiddly to get right under pressure. The two-stacks version uses no pointer and no conditionals beyond child checks; it's a plain modified preorder plus a reversal. If you value writing bug-free code in an interview over shaving memory, two stacks wins.
What order are nodes pushed onto stack1's children, and why does it matter?
Push the left child first, then the right child. Since stack1 is last-in-first-out, the right child ends up on top and is popped and processed before the left child. That yields a root-right-left visiting order, which stack2 collects and later reverses into left-right-root — postorder. If you push right before left, you get the mirror-image traversal, so this one ordering line is load-bearing.
Does the two-stacks approach handle an empty tree or a single node?
Yes, with the guard. if (!root) return [] handles the empty tree up front. For a single node, stack1 starts as [root], the first loop pops it into stack2 and finds no children, and Phase 2 pops that one node into result, returning [val]. No special-casing beyond the initial null check is required.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.