Binary Tree Postorder Traversal
Given the root of a binary tree, return the postorder traversal of its node values: left subtree, right subtree, and the node itself last.
- The number of the nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Intuition
Binary tree postorder traversal visits the left subtree, then the right, then the node itself. Recursively it is a one-line change from the other two orders — the node's append moves below both recursive calls. What makes postorder worth understanding beyond that is why it exists. A node is visited only after both its children are finished, which means children's answers are available before the parent needs them: - Postorder is the shape of almost every tree computation whose result flows upward — subtree size, height, whether a tree is balanced, evaluating an expression tree, freeing a tree safely. If you have written Maximum Depth or Diameter of Binary Tree, you have already written a postorder traversal without necessarily naming it. The iterative version is where postorder is genuinely harder than the others. Preorder is straightforward with a stack, and inorder needs a left-spine walk. Postorder appears to need a way of knowing whether you are arriving at a node for the first or second time. The elegant dodge avoids that entirely. Run a modified preorder that visits node, then right, then left, and reverse the result at the end. That reversed order is exactly left-right-node. One stack, no state flags, no second-visit detection — and considerably easier to get right under pressure than the two-stack or last-visited-pointer versions.
Children before node — the order for anything where a parent's answer depends on its subtrees' answers: deleting a tree, computing heights, evaluating an expression tree. If the node needs results from below, postorder is the traversal. Stepping through a binary tree postorder traversal visualization makes the order obvious: nothing is emitted until both subtrees are finished.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Move the append below both calls
Recurse left, recurse right, then record the node's value. That single placement is the entire difference from preorder and inorder — the same three lines in a different order.
See the base case
A null node contributes nothing, so return immediately. This terminates every branch and lets the caller recurse without checking whether each child exists.
Recognise where postorder appears
Any computation where a node's result depends on its children — height, subtree size, balance checks, expression evaluation — is postorder in disguise. Naming the pattern makes those problems familiar rather than novel.
Use reversed preorder for the iterative version
For the binary tree postorder traversal iterative form, push the root, then repeatedly pop and record, pushing left before right so right is processed first. That yields node-right-left; reverse it at the end to get left-right-node.
Understand why the reversal works
Node-right-left reversed is left-right-node, which is postorder exactly. This avoids the second-visit tracking that the direct iterative version needs, and is far easier to write correctly.
Cost of the traversal
Every node is visited once, giving O(n) time. Space is O(h) for the recursion stack, or O(n) for the iterative version's output list before reversal.
Solution & live demo
Common pitfalls
Reversing preorder without swapping the child order
preorder(root)[::-1]
dfs(node.left) dfs(node.right) res.append(node.val)
Reversed preorder is node-right-left reversed, which equals left-right-node only if you also swapped the children during the preorder. The trick works, but only as reversed root-right-left — plain reversed preorder is wrong.
Appending the value between the two recursive calls
dfs(node.left) res.append(node.val) dfs(node.right)
dfs(node.left) dfs(node.right) res.append(node.val)
That's inorder. The defining property of postorder is that a node appears only after everything beneath it, which requires both calls to complete first.
Using it where the parent must act first
# postorder to propagate a value downward
# preorder for top-down, postorder for bottom-up
Information flowing from root to leaves needs the parent processed first. Postorder gives the parent its children's results, which is the opposite direction — picking the wrong one makes the state at each node unavailable when needed.
Edge cases
Base case → empty list.
Output is left leaf, right leaf, root — parent strictly after children.
Recursion unwinds from the bottom, so the deepest node is emitted first and the root last.