Binary Tree Postorder Traversal With One Stack
Iterative binary tree postorder traversal using a single stack and a lastVisited pointer — intuition, JavaScript code, a full trace, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Postorder is the awkward sibling of the tree traversals. Preorder and inorder each have a clean iterative form with one stack, but postorder — left, right, root — forces you to hold a parent on the stack while you fully finish both of its subtrees, and only then record it. Get the bookkeeping wrong and the parent keeps diving back into a right subtree it already explored, looping forever.
The usual escape hatch is two stacks (or a reversed preorder). This post teaches the tighter one: a single stack plus one extra pointer, lastVisited, that remembers the node you just finished. That one pointer is the whole trick — it lets a parent tell "I still need to go right" apart from "I already came back from the right, pop me."
By the end you'll be able to write iterative postorder from memory and explain exactly why the lastVisited check is load-bearing.
The problem
Given the root of a binary tree, return the values of its nodes in postorder: every node appears after both its left and right subtrees. For a node, that means visit left, visit right, then the node itself.
Here's a small right-leaning tree given in level order:
Input: root = [1, null, 2, 3]
1
\
2
/
3
Output: [3, 2, 1]Read the output bottom-up: leaf 3 has no children, so it's recorded first. Its parent 2 has no right child, so 2 follows. Finally 1, whose entire right subtree (2 and 3) is done, is recorded last. Root always comes out last in postorder — which is why it's the natural traversal for "free a node only after freeing its children" style work like deleting a tree or evaluating an expression.
The brute force baseline
Recursion makes postorder trivial:
function postorderTraversal(root) {
const result = [];
function walk(node) {
if (!node) return;
walk(node.left);
walk(node.right);
result.push(node.val);
}
walk(root);
return result;
}This is correct and readable, so why look further? Because the recursion isn't free — it lives on the call stack, which you don't control. On a degenerate tree (a linked-list-shaped chain of n nodes) the recursion nests n deep, and a large enough n blows the stack with a RangeError: Maximum call stack size exceeded. Interviewers ask for the iterative version precisely to see whether you can move that hidden stack into an explicit array you manage yourself.
The key insight: remember where you just came from
Push nodes as you walk left, exactly like iterative inorder. The problem is what to do when you peek at the top of the stack. In inorder you'd pop it immediately. In postorder you can't — the node's right subtree might still be unexplored.
So a peeked node is in one of two situations:
- It has a right child you haven't processed yet → you must go right first, and leave the node on the stack.
- It has no right child, or its right child is the node you just finished → both subtrees are done, so pop and record it.
The only thing separating those two cases is memory of what you last recorded. Keep a pointer, lastVisited, set to the most recently popped node. When the top's right child equals lastVisited, you know you've just climbed back up out of that right subtree — don't re-enter it, record the parent instead. Without this pointer the parent would set curr = top.right again and loop forever.
The optimal solution
This is the exact algorithm the visualizer animates:
function postorderTraversal(root) {
const result = [];
const stack = [];
let curr = root;
let lastVisited = null;
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
const top = stack[stack.length - 1];
if (top.right && top.right !== lastVisited) {
curr = top.right;
} else {
stack.pop();
result.push(top.val);
lastVisited = top;
}
}
return result;
}Four moving parts do all the work. The inner while (curr) drills as far left as possible, pushing every node — no recording yet. Then we peek (not pop) the top. If it has an unvisited right child, we point curr at it and let the outer loop drill left down that subtree. Otherwise both sides are finished: pop, record, and update lastVisited so the parent above knows this branch is complete.
Note we peek with stack[stack.length - 1] and only pop() in the record branch. Popping too early would lose the parent we still need to return to.
Walkthrough
Tracing root = [1, null, 2, 3]. The stack is written bottom → top; curr and lastVisited are node values (or null).
| Step | curr | stack | Peeked top | Decision | lastVisited | result |
|---|---|---|---|---|---|---|
| 1 | 1 | [] | — | drill left: push 1, curr = 1.left = null | null | [] |
| 2 | null | [1] | 1 | 1.right = 2, 2 ≠ null → go right, curr = 2 | null | [] |
| 3 | 2 | [1] | — | drill left: push 2, curr = 2.left = 3 | null | [] |
| 4 | 3 | [1, 2] | — | drill left: push 3, curr = 3.left = null | null | [] |
| 5 | null | [1, 2, 3] | 3 | 3.right = null → pop, record 3 | 3 | [3] |
| 6 | null | [1, 2] | 2 | 2.right = null → pop, record 2 | 2 | [3, 2] |
| 7 | null | [1] | 1 | 1.right = 2, but 2 === lastVisited → pop, record 1 | 1 | [3, 2, 1] |
Step 7 is the payoff. Node 1's right child is 2 — normally a signal to go right — but lastVisited is 2, so we know we already finished that subtree and record 1 instead of looping. That single equality check is the difference between a correct traversal and an infinite loop.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Each node is pushed once and popped once; the peek/compare per node is O(1). |
| Space | O(h) | The stack holds at most one full root-to-leaf path, where h is tree height. |
h ranges from log n for a balanced tree to n for a degenerate chain, so worst-case space is O(n) but typical space is O(log n). This one-stack form uses roughly half the memory of the two-stack variant, which keeps a second stack the size of the output — the reason it's worth the extra lastVisited bookkeeping.
Common mistakes
- Dropping the
lastVisitedcheck. Testing onlyif (top.right)sends the parent back into a finished right subtree every time it resurfaces — an infinite loop, not a wrong answer. - Popping instead of peeking. If you
pop()the top before deciding, you lose the parent you still need when its right subtree completes. Peek first; pop only in the record branch. - Manually setting
curr = nullafter going right. Let the innerwhilehandle descent. When you docurr = top.right, the next iteration's inner loop drills left from there automatically. - Comparing values instead of references.
top.right !== lastVisitedmust compare node identity. In a tree with duplicate values, comparing.valwould falsely match unrelated nodes and corrupt the order.
Where this pattern shows up next
The "push-left, then decide at the top" skeleton is shared across all three iterative traversals — only the moment you record changes:
- Binary Tree Preorder Traversal — the recursive baseline, recording on the way down.
- Binary Tree Inorder Traversal — record between left and right; the recursion this iterative form mirrors.
- Binary Tree Preorder Traversal - Iterative — the simplest one-stack traversal, where you record on push.
- Binary Tree Inorder Traversal - Iterative — same drill-left skeleton, record on pop, no
lastVisitedneeded.
You can also step through the one-stack postorder visualizer to watch the stack, the curr pointer, and lastVisited update together on each decision.
FAQ
Why does one-stack postorder need a lastVisited pointer but inorder doesn't?
Inorder records a node the first time you peek it — left subtree done, node emitted, then move right. There's no ambiguity about whether the node is finished. Postorder must wait for the right subtree too, so a peeked node with a right child is genuinely ambiguous: have we explored right yet or not? lastVisited resolves it. When the top's right child is the node we just recorded, the right subtree is complete and we pop; otherwise we still need to descend right. Inorder never faces this choice, so it needs no such pointer.
What is the time and space complexity of iterative postorder with one stack?
Time is O(n): every node is pushed exactly once and popped exactly once, with constant work per visit. Space is O(h), where h is the tree's height, because the stack only ever holds a single root-to-leaf path. For a balanced tree that's O(log n); for a fully unbalanced chain it degrades to O(n). This is the most space-efficient iterative postorder — the two-stack version needs an extra stack proportional to the number of nodes.
How does the one-stack method avoid an infinite loop?
The loop risk is a parent repeatedly diving into a right subtree it already finished. The guard is top.right !== lastVisited. After popping and recording a node, we set lastVisited to it. When its parent later resurfaces at the top of the stack, the check sees that the parent's right child equals lastVisited, recognizes the subtree as done, and records the parent instead of pointing curr back into it. That single reference comparison is what terminates the traversal.
Should I use the one-stack or the two-stack approach in an interview?
Both are O(n) time, so pick based on what you can explain cleanly under pressure. The two-stack method (a modified preorder that you reverse) is easier to derive on the spot and harder to get subtly wrong. The one-stack method here uses less memory — O(h) versus O(n) auxiliary — and shows deeper command of the traversal. If the interviewer asks for the most space-efficient solution, reach for this one and be ready to explain the lastVisited invariant, which is exactly the detail they're probing for.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.