Binary Tree Postorder Traversal — Solution

Problem

Given the root of a binary tree, visit every node and collect the values in postorder: fully process the left subtree, then the right subtree, then the root. The root of any subtree is always the last node reported from that subtree.

[1,2,3,4,5]

• Input: root = [1, 2, 3, 4, 5]
• Output: [4, 5, 2, 3, 1]
• Explanation: left subtree yields 4 → 5 → 2, right subtree yields 3, root yields 1 last.

Compare with the single-right-child tree below — postorder here is [3, 2, 1] because node 3 (deepest left child of 2) finishes before 2 finishes before 1.

[1,null,2,null,null,3]

Intuition

Postorder is the natural order for "bottom-up" processing — a node's result depends on its children being done first. Recursion expresses this directly: define the traversal of any subtree as (left subtree) + (right subtree) + (root value), and the call stack handles the ordering automatically with no extra bookkeeping.

Solution — Recursive DFS

Recursively traverse the left subtree, then the right subtree, then append the current node's value. The base case returns immediately on a null node.

1. If the current node is null, return — this handles both empty trees and leaf boundaries.
2. Recurse into the left child.
3. Recurse into the right child.
4. Append the current node's value to the result list.
5. Return the accumulated list after the initial call returns.

1def postorderTraversal(root: "TreeNode") -> list[int]:
2    result = []
3
4    def traverse(node: "TreeNode") -> None:
5        if not node:
6            return
7        traverse(node.left)       # finish entire left subtree first
8        traverse(node.right)      # then entire right subtree
9        result.append(node.val)   # root of this subtree is always last
10
11    traverse(root)
12    return result

Time: O(n) — every node is visited exactly once. Space: O(h) — the call stack reaches the height of the tree; O(log n) for a balanced tree, O(n) for a skewed one.

Complexity Summary

Common Mistakes

• Appending the node value before recursing — that produces preorder (root → left → right), not postorder. The append must come after both recursive calls return.
• Confusing the three traversal orders — postorder is left → right → root; inorder is left → root → right; preorder is root → left → right. Postorder is the only one where the root is always last.
• Missing the null base case — without if not node: return, the recursion crashes on null children of leaf nodes. This is the single most common runtime error on tree problems.
• Returning the inner function's value instead of the outer list — in Python, the inner traverse function returns None; the result accumulates in the shared result list, which the outer function returns. Doing return traverse(root) returns None.
• Assuming the output order equals insertion order in a set or dict — the traversal order must come from the recursion structure, not from any collection with undefined iteration order.

Related Problems

• binary-tree-inorder-traversal — same recursive skeleton, just append the value between the two recursive calls instead of after
• binary-tree-preorder-traversal — same skeleton again, append before the recursive calls; comparing all three cements the pattern
• binary-tree-level-order-traversal — switches from DFS to BFS, so nodes are collected in breadth-first layers instead of depth-first postorder
• binary-tree-right-side-view — combines level-order traversal with a "last node per level" filter; builds on BFS intuition from traversal problems
• flatten-binary-tree-to-linked-list — rearranges tree nodes in-place in preorder; understanding all three DFS orders makes the required traversal obvious