Binary Tree Postorder Traversal
Problem Statement
Given the root of a binary tree, return the postorder traversal of its node values. In postorder traversal, visit the left subtree, then the right subtree, then the current node.
Input
The root pointer of a binary tree, or null for an empty tree.
Output
A list of integers in left, right, node order.
Constraints
- •
0 <= number of nodes <= 100 - •
-100 <= Node.val <= 100
Examples
Example 1
root = [1,null,2,3]
[3,2,1]Example 2
root = []
[]Learning Objectives
- Recognise postorder as the left, right, node DFS order.
- Explain why parents wait until both child subtrees finish.
- Use postorder as the bridge from traversal to subtree aggregation.
- Implement an iterative reverse-preorder or two-stack solution.
Intuition
Pattern Recognition
The signal is postorder traversal, left, right, root, or any task where a node needs both child results before acting. Visiting a node means appending its value after both the left and right subtrees have already been visited.
The common trap is visiting after only the left subtree. That produces inorder, not postorder. Postorder is children-before-parent, which is why it appears in height, diameter, balance, deletion, and tree DP problems.
Common mistakes
- ×Appending the node between left and right calls, which produces inorder.
- ×Appending immediately in a stack loop without reversing or tracking completion.
- ×Using the wrong child push order for reverse preorder.
- ×Forgetting the O(h) recursion stack in the recursive version.
Algorithm Explanation
Key idea
Postorder makes the parent last. Recursively process node.left, then node.right, then visit node. Iteratively, a compact trick is to generate node, right, left order and add every visited value to the front, reversing the stream into left, right, node.
Recursion walkthrough
Use [1,null,2,3]. Start at 1 and recurse left; that null returns. Recurse right to 2. At 2, recurse left to 3. Node 3 has two null children, so it can be visited first and the result becomes [3]. Return to 2, finish its right null, then visit 2 for [3,2]. Return to 1 and visit it last, producing [3,2,1]. With reverse preorder, the pop stream is 1,2,3, and adding each value to the front produces [3,2,1].
Algorithm
- For recursion, return on null.
- Recurse into node.left.
- Recurse into node.right.
- Append node.val after both calls return.
- For reverse preorder, push root if it exists.
- Pop a node, add its value to the front, push left, then push right.
- Stop when the stack is empty.
Solutions
Solution 1: Recursive postorder DFS
Use this when recursion is allowed. It directly communicates that the parent waits for both children.
Run a helper that returns on null, recursively finishes the left subtree, recursively finishes the right subtree, and only then appends the current value.
Step-by-step
- Create an empty result list.
- Call a helper on root.
- Return immediately for null.
- Recurse on node.left.
- Recurse on node.right.
- Add node.val after both child calls finish.
- Return the list.
O(n)
O(h)
Each node is visited once; the recursion stack grows to height **h**, O(n) for a skewed tree.
Java implementation
Solution 2: Iterative reverse-preorder stack
Use this when recursion is not allowed and a concise iterative postorder is preferred over a visited-flag stack.
Process nodes in node, right, left order while inserting each value at the front of the answer. Front insertion reverses that stream into left, right, node.
Step-by-step
- Create a linked list for results and return it if root is null.
- Push root onto the stack.
- Pop a node and add its value to the front.
- Push node.left if it exists.
- Push node.right if it exists, so right is popped before left.
- Repeat until the stack is empty.
O(n)
O(h)
Each node is pushed and popped once; the explicit stack stores O(h) pending nodes, O(n) in the worst case.
Java implementation
Dry Run
Sample input
root = [1,null,2,3]. Track reverse preorder; values are inserted at the front.
| step | popped | children pushed | stack | result after addFirst |
|---|---|---|---|---|
| start | none | push root 1 | [1] | [] |
| 1 | 1 | push right child 2 after checking left | [2] | [1] |
| 2 | 2 | push left child 3 | [3] | [2,1] |
| 3 | 3 | no children | [] | [3,2,1] |
The stack pop order is node, right, left. Adding to the front reverses it into the required left, right, node order.
Interview Tips
Describe postorder as children before parent. That phrase explains traversal and harder aggregation problems. For iterative code, name the reverse-preorder trick and justify the push order; a one-stack visited-flag solution is also valid, but longer.
Likely follow-ups
- How would you implement iterative postorder with one stack and a visited marker?
- Why is postorder useful for computing height or deleting a tree?
- How does postorder help check whether a tree is balanced?
- Can the traversal return a value from each subtree instead of appending values?
Similar Problems
Key Takeaways
- Postorder means **left, right, node**.
- The parent is visited only after both subtrees complete.
- Reverse preorder plus front insertion is a compact iterative postorder.
- Postorder is the default order for subtree aggregation.