Binary Tree Postorder Traversal: Children Before Parents
Solve Binary Tree Postorder Traversal with recursive DFS — left, then right, then root. JavaScript solution, a worked trace, 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 is the traversal that fires the parent last. Where preorder shouts a node's value the moment it arrives and inorder waits until the left subtree is done, postorder holds every node back until both of its subtrees are completely finished. That single ordering choice — children before parents — is exactly what you need whenever a node's answer depends on its descendants.
That is why postorder quietly powers deleting a tree, evaluating an expression tree, and computing subtree properties like height or diameter. By the time a node is processed, its children's results are already sitting there, ready to combine.
The problem
Given the root of a binary tree, return the values of its nodes in postorder — visit the entire left subtree, then the entire right subtree, then the node itself.
Input: root = [1, null, 2, 3]
Tree shape:
1
\
2
/
3
Output: [3, 2, 1]Read that output backwards to sanity-check the rule: 1 (the root) comes last, 2 comes right before it, and 3 — the deepest leaf — comes first. Postorder always ends with the root, no matter the shape of the tree.
The brute force baseline
There is no genuinely "brute force" version of a traversal — you have to touch every node once either way. But the naive instinct is to reach for something manual: flatten the tree into a list, sort by some rule, or hand-roll an explicit stack before you understand the recursion. All of that is more code and more room for bugs.
A tempting but wrong first attempt is to record each node as you reach it and hope the order sorts itself out:
function postorderWrong(root) {
const result = [];
function dfs(node) {
if (!node) return;
result.push(node.val); // recorded too early — this is preorder!
dfs(node.left);
dfs(node.right);
}
dfs(root);
return result;
}On [1, null, 2, 3] this returns [1, 2, 3] — the root first. That is preorder wearing a postorder label. The value isn't wrong to compute; it's recorded at the wrong moment. Postorder is entirely about when you append.
The key insight: record on the way back up
Recursion gives every node two moments: the call going down into it, and the return coming back up out of it. Postorder simply moves the push to that second moment.
Walk down the left subtree first. When it fully unwinds, walk down the right subtree. Only after both recursive calls have returned do you append the current node. Because the append happens on the way up, deepest nodes finish first and the root finishes last — leaf-to-root order falls out for free.
The mental model: postorder is a bottom-up traversal. Information flows upward. That is precisely why problems that aggregate from children — subtree sums, heights, "is this subtree balanced?" — are natural fits.
The optimal solution
Here is the exact recursive DFS the visualizer steps through: a result array, an inner dfs helper, and the base case that returns on a null node before doing anything else.
function postorderTraversal(root) {
const result = [];
function dfs(node) {
if (!node) return;
dfs(node.left);
dfs(node.right);
result.push(node.val);
}
dfs(root);
return result;
}Three lines carry all the meaning, in this order: dfs(node.left), dfs(node.right), result.push(node.val). Swap any two of them and you change the traversal:
| Order of the three lines | Traversal |
|---|---|
| push, left, right | preorder |
| left, push, right | inorder |
| left, right, push | postorder |
The base case if (!node) return is what lets you recurse into node.left and node.right without ever checking whether they exist — a null child just returns immediately and unwinds one frame.
Walkthrough
Tracing root = [1, null, 2, 3] — the same tree from the problem statement. Watch the result array: nothing gets appended until a node's subtrees are exhausted.
| Step | Action | Call stack (top →) | result |
|---|---|---|---|
| 1 | enter dfs(1) | [dfs(1)] | [] |
| 2 | dfs(1).left → null, return | [dfs(1)] | [] |
| 3 | dfs(1).right → enter dfs(2) | [dfs(1), dfs(2)] | [] |
| 4 | dfs(2).left → enter dfs(3) | [dfs(1), dfs(2), dfs(3)] | [] |
| 5 | dfs(3).left → null, return | [dfs(1), dfs(2), dfs(3)] | [] |
| 6 | dfs(3).right → null, return | [dfs(1), dfs(2), dfs(3)] | [] |
| 7 | push 3, pop dfs(3) | [dfs(1), dfs(2)] | [3] |
| 8 | dfs(2).right → null, return | [dfs(1), dfs(2)] | [3] |
| 9 | push 2, pop dfs(2) | [dfs(1)] | [3, 2] |
| 10 | push 1, pop dfs(1) | [] | [3, 2, 1] |
Node 3 is the deepest, so both of its null children return instantly and it is the first value pushed (step 7). Node 2 waits for its whole subtree — 3 on the left, nothing on the right — before pushing (step 9). The root 1 pushes dead last (step 10), which is the postorder signature.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Every node is entered once and pushed once; the null-child returns are also bounded by O(n). |
| Space | O(h) | The recursion call stack holds one frame per ancestor, so it's the tree height h. |
For a balanced tree h ≈ log n, so space is O(log n). For a fully skewed tree — a linked list in disguise — h = n and the stack grows to O(n), which is also when recursion risks a stack overflow. The output array is O(n) on top of the stack, but that's required output, not working space.
Common mistakes
- Pushing at the wrong line. Appending before the recursive calls gives preorder; appending between them gives inorder. Postorder appends after both
dfs(node.left)anddfs(node.right). - Forgetting the null base case. Without
if (!node) return, recursing into a null child throws when you readnode.left. The base case is what makes the leaf-handling implicit. - Reversing left and right.
dfs(node.right)beforedfs(node.left)produces a mirror-image "reverse postorder," not the standard result. Left always goes first. - Assuming the stack is free. On a degenerate skewed tree the recursion depth is O(n); very tall trees can blow the stack, which is the practical reason the iterative one-stack and two-stack variants exist.
- Reading the output top-down. Postorder output is bottom-up. The last element is the root, not the first — the opposite of preorder.
Where this pattern shows up next
Postorder is one of three sibling DFS orderings, and the fastest way to internalize it is to compare where the push lands in each:
- Binary Tree Preorder Traversal — root first, the mirror image of this problem.
- Binary Tree Inorder Traversal — root in the middle, which yields sorted order on a BST.
- Binary Tree Preorder Traversal - Iterative — the same order without recursion, using an explicit stack.
- Binary Tree Inorder Traversal - Iterative — the trickier explicit-stack version where you push left, then process.
To watch the call stack grow and the result fill leaf-first, step through the Binary Tree Postorder Traversal visualizer one frame at a time.
FAQ
What order does postorder traversal visit nodes in?
Left subtree, then right subtree, then the node itself — often abbreviated Left → Right → Root. Every node is recorded only after both of its subtrees are fully processed, so the deepest leaves appear first in the output and the root always appears last. On the tree [1, null, 2, 3], postorder produces [3, 2, 1].
Why would I use postorder instead of preorder or inorder?
Use postorder whenever a node's result depends on its children's results — a bottom-up computation. Deleting a tree requires freeing children before the parent, evaluating an expression tree requires both operands before the operator, and computing height, subtree sums, or "is this balanced?" all need the child answers ready before the parent runs. Postorder guarantees exactly that ordering.
What is the time and space complexity of postorder traversal?
Time is O(n) because each of the n nodes is entered and appended exactly once. Space is O(h), where h is the height of the tree, for the recursion call stack: O(log n) for a balanced tree and O(n) in the worst case of a completely skewed tree. The returned result array adds O(n), but that is required output rather than auxiliary working memory.
How is postorder different from preorder in code?
Only the placement of one line changes. Preorder pushes the node's value before recursing into its children; postorder pushes it after both recursive calls return. Same helper, same base case, same traversal of the tree — the sole difference is that result.push(node.val) moves from the top of the function to the bottom, which flips the output from top-down to bottom-up.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.