Construct from Preorder and Inorder
Mahabharata — The Reconstruction — Rebuilding the Tree from Two Traversal Records
Preorder का पहला — root है। Inorder में root ढूँढो — बायाँ और दायाँ विभाजित करो॥
*Preorder's first — is the root. Find root in inorder — split into left and right.*
The Story
Construct a binary tree from preorder and inorder traversal arrays.
For `preorder=[3,9,20,15,7]`, `inorder=[9,3,15,20,7]`: tree is `[3,9,20,null,null,15,7]`.
**Algorithm:** - `preorder[0]` is always the root - Find the root in inorder: everything to the left = left subtree, everything to the right = right subtree - Recursively build left and right subtrees
```java Map<Integer,Integer> inMap = new HashMap<>(); for (int i=0;i<inorder.length;i++) inMap.put(inorder[i], i);
TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) { if (preStart > preEnd) return null; int rootVal = pre[preStart]; // First in preorder = root TreeNode root = new TreeNode(rootVal); int inIdx = inMap.get(rootVal); // Root's position in inorder int leftSize = inIdx - inStart; // Size of left subtree root.left = build(pre, preStart+1, preStart+leftSize, in, inStart, inIdx-1); root.right = build(pre, preStart+leftSize+1, preEnd, in, inIdx+1, inEnd); return root; } ```
Trace `pre=[3,9,20,15,7]`, `in=[9,3,15,20,7]`: - root=3. inIdx=1. leftSize=1. - Left: pre[1..1]=[9], in[0..0]=[9]. root=9, no children. - Right: pre[2..4]=[20,15,7], in[2..4]=[15,20,7]. root=20. inIdx=3(pos of 20 in in)=3. leftSize=3-2=1. - Left: pre[3..3]=[15], in[2..2]=[15]. root=15. - Right: pre[4..4]=[7], in[4..4]=[7]. root=7. - Tree: [3,9,20,null,null,15,7] ✓
The Without-HashMap Approach
Find root in inorder by linear scan each time. O(n²). HashMap makes lookup O(1) → O(n) overall.
TreeNode buildWithoutMap(int[] pre, int ps, int pe, int[] in, int is, int ie) {
if (ps > pe) return null;
TreeNode root = new TreeNode(pre[ps]);
int idx = is;
while (in[idx] != pre[ps]) idx++; // O(n) per call → O(n²) total
int leftSize = idx - is;
root.left = buildWithoutMap(pre, ps+1, ps+leftSize, in, is, idx-1);
root.right = buildWithoutMap(pre, ps+leftSize+1, pe, in, idx+1, ie);
return root;
}The HashMap+Index-Range Recursion Wisdom
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, inMap);
}
TreeNode build(int[] pre, int ps, int pe, int[] in, int is, int ie, Map<Integer,Integer> inMap) {
if (ps > pe) return null;
TreeNode root = new TreeNode(pre[ps]);
int inIdx = inMap.get(pre[ps]);
int leftSize = inIdx - is;
root.left = build(pre, ps+1, ps+leftSize, in, is, inIdx-1, inMap);
root.right = build(pre, ps+leftSize+1, pe, in, inIdx+1, ie, inMap);
return root;
}Step-by-Step Walkthrough
pre=[1], in=[1]: ps=pe=0. root=1. inIdx=0. leftSize=0. Left: ps=1>pe=0 → null. Right: null. Return single node 1. ✅
Deep Insight
**The leftSize calculation:** leftSize = inIdx - inStart. This is the number of elements in the left subtree (from inStart to inIdx-1). This tells us exactly how many preorder elements to assign to the left subtree (preStart+1 to preStart+leftSize).
**Why unique values required:** The HashMap lookup assumes each value appears once. With duplicates, the root position in inorder is ambiguous.
**tr-32 (Postorder+Inorder) is the mirror:** Last element of postorder is root. Same inorder split logic, but index arithmetic is mirrored.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | O(n) inorder search × n recursive calls |
| Optimal | O(n) | O(n) | HashMap lookup O(1); n calls × O(1) each |
Pattern Recognition
✅ Construct from preorder+inorder: pre[0]=root ✅ HashMap: inorder value → index ✅ leftSize = inIdx - inStart ✅ Recurse on index ranges **LeetCode Trigger Phrases:** → "construct binary tree from preorder and inorder" → Reconstruction from two traversals → pre[0]=root + inorder split
Bhagavad Gita 13.12
अनादिमत्परं ब्रह्म न सत्तन्नासदुच्यते।
The Supreme Brahman is beginningless and supreme. It is said to be neither being nor non-being.
Connection: The tree reconstruction from traversals is like knowing the absolute truth from two different perspectives. Preorder reveals the hierarchical structure (root first, commanders before troops). Inorder reveals the ordered essence (left-root-right, value order). From these two perspectives combined, the unique tree (the true structure) can be perfectly reconstructed. No information is lost — the two traversals together contain the complete truth of the tree.