Problem Statement
Given the root of a binary tree, return its postorder traversal.
Postorder Traversal follows:
Left
↓
Right
↓
Root
Brute Force Intuition
In an interview, you can explain it like this:
Recursively traverse the left subtree, then the right subtree, and finally visit the current node.
Recursion naturally ensures that a node is processed only after both of its children.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(H)
Where:
-
N= Number of Nodes -
H= Height of the Tree
Recursive Code
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
postorder(root, ans);
return ans;
}
private void postorder(TreeNode root,
List<Integer> ans) {
if (root == null)
return;
postorder(root.left, ans);
postorder(root.right, ans);
ans.add(root.val);
}
}
Moving Towards the Optimal Iterative Approach
Postorder is tricky because the root should be visited last.
Instead of directly following:
Left
↓
Right
↓
Root
we can generate:
Root
↓
Right
↓
Left
and reverse the final answer.
Pattern Recognition
Whenever you see:
- Postorder Traversal
- Simulate Recursion
Think:
Stack + Reverse
Key Observation
Preorder is:
Root
↓
Left
↓
Right
If we instead visit:
Root
↓
Right
↓
Left
then reversing the result gives:
Left
↓
Right
↓
Root
which is exactly Postorder.
Optimal Java Solution
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if (root == null)
return ans;
Stack<TreeNode> st = new Stack<>();
st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.pop();
ans.addFirst(node.val);
if (node.left != null)
st.push(node.left);
if (node.right != null)
st.push(node.right);
}
return ans;
}
}
Dry Run
1
/ \
2 3
/ \
4 5
Stack:
1
Visit:
1
Answer:
1
Push:
2
3
Visit:
3
Answer:
3 1
Visit:
2
Answer:
2 3 1
Visit:
5
Answer:
5 2 3 1
Visit:
4
Answer:
4 5 2 3 1
Final Postorder:
[4,5,2,3,1]
Why Stack + Reverse Works?
We intentionally generate:
Root
↓
Right
↓
Left
Since we insert every node at the beginning of the answer,
the final order becomes:
Left
↓
Right
↓
Root
which is exactly Postorder Traversal.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(H) |
Interview One-Liner
Traverse the tree in Root → Right → Left order using a stack, then reverse the traversal by inserting each node at the front of the answer.
Pattern Learned
Root
↓
Right
↓
Left
↓
Reverse
↓
Left
↓
Right
↓
Root
Similar Problems
- Postorder Traversal
- Binary Tree Paths
- Flatten Binary Tree
- Serialize and Deserialize Binary Tree
Memory Trick
Think:
Reverse Preorder
↓
Root
↓
Right
↓
Left
↓
Reverse Answer
Mental Model
Normal Preorder
Root
↓
Left
↓
Right
------------------
Modified
Root
↓
Right
↓
Left
↓
Reverse
↓
Postorder
Whenever you hear:
"Iterative Postorder Traversal"
your brain should immediately think:
Modified Preorder + Reverse
Top comments (0)