Construct from Preorder and Postorder
Mahabharata — The Two-Ended Reconstruction — Root Known from Both Ends, Left Root from Middle
Pre का पहला root — Post का अंतिम root। Pre का दूसरा — left subtree root — Post में ढूँढो॥
*Pre's first is root — Post's last is root. Pre's second — left subtree root — find in Post.*
The Story
Construct a binary tree from preorder and postorder traversal arrays. Note: multiple valid trees may exist if some nodes have only one child.
For `preorder=[1,2,4,5,3,6,7]`, `postorder=[4,5,2,6,7,3,1]`: tree is `[1,2,3,4,5,6,7]`.
**Algorithm:** - `pre[preStart]` = root - `pre[preStart+1]` = root of the left subtree (if left subtree exists) - Find `pre[preStart+1]` in postorder: its position tells us the left subtree size - `leftSize = postIdx - postStart + 1` - Recurse on left and right
```java Map<Integer,Integer> postMap = new HashMap<>(); for (int i=0;i<post.length;i++) postMap.put(post[i],i);
TreeNode build(int[] pre, int ps, int pe, int[] post, int poStart, int poEnd) { if (ps > pe) return null; TreeNode root = new TreeNode(pre[ps]); if (ps == pe) return root; // Leaf int leftRootVal = pre[ps+1]; // Left subtree root int postIdx = postMap.get(leftRootVal); // Its position in postorder int leftSize = postIdx - poStart + 1; root.left = build(pre, ps+1, ps+leftSize, post, poStart, postIdx); root.right = build(pre, ps+leftSize+1, pe, post, postIdx+1, poEnd-1); return root; } ```
Trace `pre=[1,2,4,5,3,6,7]`, `post=[4,5,2,6,7,3,1]`: - root=1. leftRoot=pre[1]=2. postIdx=2 (pos of 2 in post). leftSize=2-0+1=3. - Left: pre[1..3]=[2,4,5], post[0..2]=[4,5,2]. root=2. leftRoot=4. postIdx=0. leftSize=1. - Left: pre[2..2]=[4], post[0..0]=[4]. Leaf 4. - Right: pre[3..3]=[5], post[1..1]=[5]. Leaf 5. - Right: pre[4..6]=[3,6,7], post[3..5]=[6,7,3]. root=3. leftRoot=6. postIdx=3. leftSize=1. - Left: leaf 6. Right: leaf 7. - Tree: [1,2,3,4,5,6,7] ✓
The Without-HashMap Approach
Linear scan for leftRoot in postorder each time. O(n²).
// O(n²): linear scan for leftRoot in post each time
// The HashMap approach is O(n)The Two-Root + PostMap Wisdom
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
Map<Integer, Integer> postMap = new HashMap<>();
for (int i = 0; i < postorder.length; i++) postMap.put(postorder[i], i);
return build(preorder, 0, preorder.length-1, postorder, 0, postorder.length-1, postMap);
}
TreeNode build(int[] pre, int ps, int pe, int[] post, int poS, int poE, Map<Integer,Integer> postMap) {
if (ps > pe) return null;
TreeNode root = new TreeNode(pre[ps]);
if (ps == pe) return root;
int leftRootVal = pre[ps + 1];
int postIdx = postMap.get(leftRootVal);
int leftSize = postIdx - poS + 1;
root.left = build(pre, ps+1, ps+leftSize, post, poS, postIdx, postMap);
root.right = build(pre, ps+leftSize+1, pe, post, postIdx+1, poE-1, postMap);
return root;
}Step-by-Step Walkthrough
pre=[1], post=[1]: ps==pe → return leaf 1. ✅
Deep Insight
**Why pre[ps+1]?** In preorder, after the root, the next element is the root of the left subtree. Finding this left subtree root in postorder tells us where the left subtree ends (since it's the last element before the right subtree in postorder).
**Non-uniqueness:** If a node has only one child, we can't tell if it's left or right from preorder+postorder alone. The algorithm arbitrarily places it as left. Any valid tree is accepted.
**leftSize = postIdx - poStart + 1:** The left subtree in postorder spans from poStart to postIdx. The number of elements = postIdx - poStart + 1.
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
✅ Preorder+Postorder: pre[ps]=root, pre[ps+1]=leftRoot ✅ Find leftRoot in postMap → leftSize ✅ Non-unique when single-child nodes exist ✅ leftSize = postIdx - poStart + 1 **LeetCode Trigger Phrases:** → "construct from preorder and postorder" → pre[0]=root, post[last]=root, pre[1]=leftRoot → Non-unique reconstruction
Bhagavad Gita 11.16
पश्यामि त्वां सर्वतो ऽनन्तरूपं नान्तं न मध्यं न पुनस्तवादिम्।
I see You everywhere, infinite in form, neither end, nor middle, nor beginning do I see.
Connection: Construction from preorder and postorder requires knowing both the first (pre) and last (post) simultaneously — no beginning, no end, only the middle boundaries of each subtree. Like Arjuna's vision of Krishna's infinite form where no single starting or ending point could be identified, the tree reconstruction triangulates from both extremes (first of pre, last of post, and the second of pre as left root) to reconstruct the complete structure.