Construct from Postorder and Inorder
Mahabharata — The Bottom-Up Reconstruction — Last in Postorder is Root
Postorder का अंतिम — root है। Inorder में विभाजित करो — बायाँ और दायाँ॥
*Postorder's last — is the root. Split in inorder — left and right.*
The Story
Construct a binary tree from inorder and postorder traversal arrays.
For `inorder=[9,3,15,20,7]`, `postorder=[9,15,7,20,3]`: tree is `[3,9,20,null,null,15,7]`.
**Algorithm (mirror of tr-31):** - `postorder[last]` is always the root - Find the root in inorder: split into left and right subtrees - Recursively build right first, then left (postorder processes right subtree BEFORE left in the array)
```java Map<Integer,Integer> inMap = new HashMap<>(); for (int i=0;i<inorder.length;i++) inMap.put(inorder[i],i);
TreeNode build(int[] post, int ps, int pe, int[] in, int is, int ie) { if (ps > pe) return null; int rootVal = post[pe]; // LAST in postorder = root TreeNode root = new TreeNode(rootVal); int inIdx = inMap.get(rootVal); int leftSize = inIdx - is; root.left = build(post, ps, ps+leftSize-1, in, is, inIdx-1); root.right = build(post, ps+leftSize, pe-1, in, inIdx+1, ie); return root; } ```
Trace `in=[9,3,15,20,7]`, `post=[9,15,7,20,3]`: - root=post[4]=3. inIdx=1. leftSize=1. - Left: post[0..0]=[9], in[0..0]=[9]. root=9. - Right: post[1..3]=[15,7,20], in[2..4]=[15,20,7]. root=20. inIdx=3. leftSize=1. - Left: post[1..1]=[15], in[2..2]=[15]. root=15. - Right: post[2..2]=[7], in[4..4]=[7]. root=7. - Tree: [3,9,20,null,null,15,7] ✓
The Without-HashMap Approach
Linear scan for root in inorder each time. O(n²).
TreeNode buildSlow(int[] in, int is, int ie, int[] post, int ps, int pe) {
if (ps > pe) return null;
TreeNode root = new TreeNode(post[pe]);
int idx = is;
while (in[idx] != post[pe]) idx++;
int leftSize = idx - is;
root.left = buildSlow(in, is, idx-1, post, ps, ps+leftSize-1);
root.right = buildSlow(in, idx+1, ie, post, ps+leftSize, pe-1);
return root;
}The post[pe]=root + HashMap Split Wisdom
public TreeNode buildTree(int[] inorder, int[] postorder) {
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
return build(postorder, 0, postorder.length-1, inorder, 0, inorder.length-1, inMap);
}
TreeNode build(int[] post, int ps, int pe, int[] in, int is, int ie, Map<Integer,Integer> inMap) {
if (ps > pe) return null;
TreeNode root = new TreeNode(post[pe]);
int inIdx = inMap.get(post[pe]);
int leftSize = inIdx - is;
root.left = build(post, ps, ps+leftSize-1, in, is, inIdx-1, inMap);
root.right = build(post, ps+leftSize, pe-1, in, inIdx+1, ie, inMap);
return root;
}Step-by-Step Walkthrough
in=[2,1,3], post=[2,3,1]: root=1. inIdx=1. leftSize=1. Left:post[0..0]=[2],in[0..0]=[2]. Right:post[1..1]=[3],in[2..2]=[3]. Tree=[1,2,3] ✅
Deep Insight
**Preorder+Inorder vs Postorder+Inorder:** - Preorder: first element = root; pre[ps+1..ps+leftSize] = left; pre[ps+leftSize+1..pe] = right - Postorder: last element = root; post[ps..ps+leftSize-1] = left; post[ps+leftSize..pe-1] = right
The index arithmetic is the mirror image. The inorder split logic is identical.
**Why postorder: build right first?** In the postorder array, right subtree elements come before left (since postorder is L-R-Root, the root comes last, and right subtree elements appear right before root). But in my implementation I compute leftSize first from inorder, so the order doesn't matter.
**Can we reconstruct from preorder+postorder without inorder? (tr-33):** Yes, but the tree is not unique when nodes have only one child.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Linear scan per call |
| Optimal | O(n) | O(n) | HashMap O(1) lookup; n recursive calls |
Pattern Recognition
✅ Postorder+Inorder: post[pe]=root ✅ Same inorder split as preorder+inorder ✅ leftSize = inIdx - is ✅ Mirror of tr-31 **LeetCode Trigger Phrases:** → "construct binary tree from inorder and postorder" → post[last]=root + inorder split → Mirror of preorder construction
Bhagavad Gita 13.13
सर्वतः पाणिपादं तत् सर्वतोऽक्षिशिरोमुखम्। सर्वतः श्रुतिमल्लोके सर्वमावृत्य तिष्ठति॥
With hands and feet everywhere, with eyes, heads, and faces everywhere, with ears everywhere — it stands pervading everything in the world.
Connection: From the bottom (postorder last = root), the tree is reconstructed back to its original form. Like the omnipresent divine who can be approached from any angle and yet remains the same unified truth, the binary tree can be reconstructed from either preorder+inorder or postorder+inorder. Both approaches arrive at the same tree — the same truth revealed through different traversal sequences.