Postorder Traversal
Mahabharata — The Final Reckoning — Left, Then Right, Then the Root Last
बायां — दायां — फिर मूल अंत में। Postorder में — संतान पहले, जनक बाद में॥
*Left — right — then root at the end. In postorder — children first, parent after.*
The Story
Perform postorder traversal (Left → Right → Root) of a binary tree.
For tree `[1,2,3]`: Postorder=[2,3,1].
**Recursive:** ```java void postorder(TreeNode root, List<Integer> res) { if (root == null) return; postorder(root.left, res); // Left first postorder(root.right, res); // Right res.add(root.val); // Root last } ```
**Iterative trick — Reverse of modified preorder:** Modified preorder (Root → Right → Left) reversed = Left → Right → Root = Postorder!
```java LinkedList<Integer> res = new LinkedList<>(); // addFirst to build in reverse Deque<TreeNode> st = new ArrayDeque<>(); st.push(root); while (!st.isEmpty()) { root = st.pop(); res.addFirst(root.val); // Prepend (build in reverse) if (root.left != null) st.push(root.left); // Left pushed BEFORE right if (root.right != null) st.push(root.right); // Right pops first → Root,Right,Left } // res is now Left,Right,Root = Postorder ```
**Use cases for postorder:** - Delete a tree (delete children before parent) - Evaluate expression tree (compute children before operator) - Calculate directory sizes (subdirectory sizes before folder) - "Bottom-up" tree DP problems
Trace `[1,2,3]` with reverse-preorder: - Push 1. Pop 1, addFirst(1), push 2(left), push 3(right). - Pop 3, addFirst(3), no children. - Pop 2, addFirst(2), no children. - res=[2,3,1] ✓ (reverse of [1,3,2])
The Recursive Approach
Recursive postorder is already O(n). The iterative reverse-of-preorder is an elegant trick.
public List<Integer> postorderRecursive(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
postorderHelper(root, res);
return res;
}
void postorderHelper(TreeNode root, List<Integer> res) {
if (root == null) return;
postorderHelper(root.left, res);
postorderHelper(root.right, res);
res.add(root.val);
}The Reverse-Preorder Wisdom
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) return res;
Deque<TreeNode> st = new ArrayDeque<>();
st.push(root);
while (!st.isEmpty()) {
root = st.pop();
res.addFirst(root.val); // Prepend
if (root.left != null) st.push(root.left);
if (root.right != null) st.push(root.right);
}
return res;
}Step-by-Step Walkthrough
Single node [1]: push 1. Pop 1, addFirst(1). Stack empty. Result=[1] ✅
Deep Insight
**The three traversals in one pattern:** - Preorder: Visit, push right, push left → `res.add` - Postorder: Visit with addFirst, push left, push right → builds in reverse - Both use the same stack-based push pattern — just mirror the push order and use addFirst
**Postorder is 'bottom-up':** Children are fully processed before the parent. This is essential for: - Tree height calculation (children heights needed to compute parent height) - Tree diameter - Lowest Common Ancestor - Expression tree evaluation
**Alternative iterative postorder:** Two-pass (inorder-like) with explicit state tracking. The reverse-preorder trick is simpler.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Recursive call stack |
| Optimal | O(n) | O(n) | Iterative stack |
Pattern Recognition
✅ Postorder = Left, Right, Root ✅ Iterative trick: reverse of modified preorder ✅ push left BEFORE right (right pops first) ✅ addFirst() builds in reverse → postorder order **LeetCode Trigger Phrases:** → "postorder traversal" → Process children before parent → Bottom-up tree computation
Bhagavad Gita 15.1
मूलान्यव्यक्तमाहुः पुरुषं परमम्।
With roots above and branches below, the imperishable Ashvattha tree is spoken of; its roots are the Primal Person.
Connection: Postorder traversal honors the roots last — the children are visited before the parent, the branches before the trunk, the leaves before the tree itself. Like the Ashvattha tree described in the Gita with its roots above (the source, visited last in postorder) and branches below (the descendants, visited first), postorder traversal processes from the bottom up, recognizing that understanding must come from the leaves to arrive at the root.