149. Construct Binary Tree from Preorder and Inorder Traversal
š LeetCode Problem: 105. Construct Binary Tree from Preorder and Inorder Traversal
š Difficulty: Medium
š·ļø Topics: Binary Trees, Array, Divide and Conquer, Recursion, HashMap
Problem Statement
Given two integer arrays preorder and inorder where:
- preorder is the preorder traversal of a binary tree
- inorder is the inorder traversal of the same tree
Construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Constraints:
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values
- Each value of inorder also appears in preorder
- preorder is guaranteed to be the preorder traversal of the tree
- inorder is guaranteed to be the inorder traversal of the tree
š³ Visual Understanding - How Traversals Encode Trees
Traversal Definitions Recap:
PREORDER (Root ā Left ā Right):
Process root FIRST
Then entire left subtree
Then entire right subtree
INORDER (Left ā Root ā Right):
Process left subtree FIRST
Then root
Then right subtree
The Key Insight - What Each Traversal Tells Us:
PREORDER tells us:
- First element = ROOT
- Next elements = left subtree (but mixed together)
- Last elements = right subtree (but mixed together)
INORDER tells us:
- Elements before root = left subtree
- Root in middle
- Elements after root = right subtree
Together they UNIQUELY determine the tree! š
Example 1 - Visual Breakdown:
Given:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
STEP 1: Find root from preorder
preorder[0] = 3
Root = 3 ā
STEP 2: Find root in inorder
inorder = [9, | 3 |, 15, 20, 7]
ā ā ā
left root right
STEP 3: Partition inorder
Left subtree: [9]
Right subtree: [15, 20, 7]
STEP 4: Partition preorder accordingly
Root: 3
Left: [9] (next 1 element after root)
Right: [20, 15, 7] (remaining elements)
STEP 5: Current tree structure
3
/ \
? ?
/ \
[9] [15,20,7]
Recursively build left and right!
Visual Tree Construction:
Step 1: Root = 3
3
Step 2: Build left subtree from [9] and [9]
Root = 9 (no children)
3
/
9
Step 3: Build right subtree from [20,15,7] and [15,20,7]
Root = 20
Left = [15]
Right = [7]
3
/ \
9 20
/ \
15 7
Final tree! ā
Another Example - Understanding Partitioning:
preorder = [1, 2, 4, 5, 3]
inorder = [4, 2, 5, 1, 3]
STEP 1: Root = 1 (first in preorder)
STEP 2: Find 1 in inorder
[4, 2, 5, | 1 |, 3]
ā ā ā
left root right
STEP 3: Left subtree has 3 elements: [4, 2, 5]
Right subtree has 1 element: [3]
STEP 4: Split preorder:
Skip root (1)
Take next 3 for left: [2, 4, 5]
Take remaining for right: [3]
STEP 5: Recursively build:
Left: preorder=[2,4,5], inorder=[4,2,5]
Right: preorder=[3], inorder=[3]
Tree:
1
/ \
2 3
/ \
4 5
š§ The AHA Moment - The Algorithm
The Core Algorithm:
buildTree(preorder, inorder):
1. Root = preorder[0]
2. Find root index in inorder
3. Elements before root in inorder = left subtree
4. Elements after root in inorder = right subtree
5. Partition preorder based on left subtree size
6. Recursively build left and right subtrees
7. Connect and return
Divide and conquer! šÆ
Visual Algorithm Flow:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
ā Find root: preorder[0] = 3 ā
ā Find in inorder: index 1 ā
ā ā
ā Partition inorder: ā
ā Left: [9] (indices 0-0) ā
ā Right: [15,20,7] (indices 2-4) ā
ā ā
ā Partition preorder: ā
ā Left size = 1 ā
ā Left: [9] (indices 1-1) ā
ā Right: [20,15,7] (indices 2-4) ā
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
ā
Recurse on left and right
š§ Recursive Thinking - Building the Solution
Base Case:
When to stop?
ā When preorder or inorder is empty
What to return?
ā null (no tree)
if (preStart > preEnd) return null;
// OR
if (inStart > inEnd) return null;
Recursive Case:
For any valid range:
STEP 1: Create root from preorder
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
STEP 2: Find root in inorder
int rootIndex = findInInorder(rootVal);
STEP 3: Calculate left subtree size
int leftSize = rootIndex - inStart;
STEP 4: Recursively build left subtree
root.left = buildTree(
preorder, preStart + 1, preStart + leftSize,
inorder, inStart, rootIndex - 1
);
STEP 5: Recursively build right subtree
root.right = buildTree(
preorder, preStart + leftSize + 1, preEnd,
inorder, rootIndex + 1, inEnd
);
STEP 6: Return constructed root
return root;
What Each Call Returns:
Each recursive call returns:
A TreeNode that is the root of a subtree
Parent connects this to:
- root.left (if left subtree)
- root.right (if right subtree)
Example:
buildTree([9], [9]) returns:
TreeNode(9)
Parent uses this:
root.left = TreeNode(9)
šÆ Solution: Divide and Conquer with HashMap
Implementation:
class Solution {
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// Build hashmap for O(1) lookup of root in inorder
// WHY? We'll search for root many times
inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
// Start recursive building
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
// Base case: no elements to construct tree
if (preStart > preEnd || inStart > inEnd) {
return null;
}
// STEP 1: First element in preorder is root
// WHY? Preorder visits root first!
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// STEP 2: Find root position in inorder
// WHY? Inorder tells us left vs right split
int rootIndex = inorderMap.get(rootVal);
// STEP 3: Calculate left subtree size
// WHY? Need to know how to split preorder array
int leftSize = rootIndex - inStart;
// STEP 4: Recursively build left subtree
// Preorder: skip root, take next 'leftSize' elements
// Inorder: elements before root
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, rootIndex - 1);
// STEP 5: Recursively build right subtree
// Preorder: elements after left subtree
// Inorder: elements after root
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, rootIndex + 1, inEnd);
// STEP 6: Return constructed subtree
return root;
}
}
Why HashMap?
Without HashMap:
For each node, search for root in inorder: O(n)
Total: O(n) nodes Ć O(n) search = O(nĀ²)
With HashMap:
Precompute all positions: O(n) once
Lookup for each node: O(1)
Total: O(n) ā
Optimization from O(nĀ²) to O(n)! š
š Detailed Dry Run - Complete Recursion
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
inorderMap = {9:0, 3:1, 15:2, 20:3, 7:4}
Complete Call Stack Visualization:
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
CALL STACK - BUILDING THE TREE
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Level 0: build(pre[0-4], in[0-4])
ā
āā rootVal = preorder[0] = 3
āā Create node: TreeNode(3)
āā rootIndex = inorderMap.get(3) = 1
āā leftSize = 1 - 0 = 1
ā
āā LEFT: build(pre[1-1], in[0-0]) āāāāāāāāāāāāāāāāā
ā ā
ā Level 1: build(pre[1-1], in[0-0]) ā
ā ā ā
ā āā preStart=1, preEnd=1 ā
ā āā inStart=0, inEnd=0 ā
ā ā ā
ā āā rootVal = preorder[1] = 9 ā
ā āā Create node: TreeNode(9) ā
ā āā rootIndex = inorderMap.get(9) = 0 ā
ā āā leftSize = 0 - 0 = 0 ā
ā ā ā
ā āā LEFT: build(pre[2-1], in[0--1]) ā
ā ā ā preStart > preEnd ā return null ā
ā ā ā
ā āā RIGHT: build(pre[2-1], in[1-0]) ā
ā ā ā preStart > preEnd ā return null ā
ā ā ā
ā āā return TreeNode(9) ā
ā āā Node structure: 9 ā
ā / \ ā
ā null null ā
ā ā
āā 3.left = TreeNode(9) ā
ā ā
āā RIGHT: build(pre[2-4], in[2-4]) āāāāāāāāāāāāāāāā
ā ā
ā Level 1: build(pre[2-4], in[2-4]) ā
ā ā ā
ā āā preStart=2, preEnd=4 ā
ā āā inStart=2, inEnd=4 ā
ā ā ā
ā āā rootVal = preorder[2] = 20 ā
ā āā Create node: TreeNode(20) ā
ā āā rootIndex = inorderMap.get(20) = 3 ā
ā āā leftSize = 3 - 2 = 1 ā
ā ā ā
ā āā LEFT: build(pre[3-3], in[2-2]) āāāāāāāā ā
ā ā ā ā
ā ā Level 2: build(pre[3-3], in[2-2]) ā ā
ā ā ā ā ā
ā ā āā rootVal = preorder[3] = 15 ā ā
ā ā āā Create node: TreeNode(15) ā ā
ā ā āā rootIndex = 2 ā ā
ā ā āā leftSize = 0 ā ā
ā ā ā ā ā
ā ā āā LEFT: null ā ā
ā ā āā RIGHT: null ā ā
ā ā ā ā ā
ā ā āā return TreeNode(15) ā ā
ā ā ā ā
ā āā 20.left = TreeNode(15) ā ā
ā ā ā
ā āā RIGHT: build(pre[4-4], in[4-4]) āāāāāāā ā
ā ā ā ā
ā ā Level 2: build(pre[4-4], in[4-4]) ā ā
ā ā ā ā ā
ā ā āā rootVal = preorder[4] = 7 ā ā
ā ā āā Create node: TreeNode(7) ā ā
ā ā āā rootIndex = 4 ā ā
ā ā āā leftSize = 0 ā ā
ā ā ā ā ā
ā ā āā LEFT: null ā ā
ā ā āā RIGHT: null ā ā
ā ā ā ā ā
ā ā āā return TreeNode(7) ā ā
ā ā ā ā
ā āā 20.right = TreeNode(7) ā ā
ā ā ā
ā āā return TreeNode(20) ā
ā āā Node structure: 20 ā
ā / \ ā
ā 15 7 ā
ā ā
āā 3.right = TreeNode(20) ā
ā ā
āā return TreeNode(3) ā
āā Final tree: 3 ā
/ \ ā
9 20 ā
/ \ ā
15 7 ā
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
FINAL RESULT: Complete binary tree constructed! ā
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
Array Indices at Each Step:
LEVEL 0: Root = 3
preorder indices [0-4]: [3, 9, 20, 15, 7]
inorder indices [0-4]: [9, 3, 15, 20, 7]
Root found at inorder[1]
Left subtree: 1 element
Right subtree: 3 elements
LEVEL 1 (Left): Root = 9
preorder indices [1-1]: [9]
inorder indices [0-0]: [9]
No children ā leaf node
LEVEL 1 (Right): Root = 20
preorder indices [2-4]: [20, 15, 7]
inorder indices [2-4]: [15, 20, 7]
Root found at inorder[3]
Left subtree: 1 element
Right subtree: 1 element
LEVEL 2 (Left of 20): Root = 15
preorder indices [3-3]: [15]
inorder indices [2-2]: [15]
No children ā leaf node
LEVEL 2 (Right of 20): Root = 7
preorder indices [4-4]: [7]
inorder indices [4-4]: [7]
No children ā leaf node
š Visual Index Calculations
Understanding the Index Math:
Given:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
ā ā
idx 0 idx 1 (root)
At root (3):
rootIndex in inorder = 1
inStart = 0
leftSize = rootIndex - inStart = 1 - 0 = 1
Preorder partitioning:
Root: preorder[0] = 3
Left: preorder[1 to 1+leftSize-1]
= preorder[1 to 1]
= [9]
Right: preorder[1+leftSize to end]
= preorder[2 to 4]
= [20, 15, 7]
Inorder partitioning:
Left: inorder[0 to rootIndex-1]
= inorder[0 to 0]
= [9]
Right: inorder[rootIndex+1 to end]
= inorder[2 to 4]
= [15, 20, 7]
Why leftSize is Critical:
leftSize tells us:
- How many elements in left subtree
- Where to split preorder array
Without it, we can't partition preorder correctly!
Example:
inorder = [4, 2, 5, 1, 3]
ā--------ā ā
left root right
leftSize = 3 (three elements before root)
preorder = [1, 2, 4, 5, 3]
ā--------ā ā
left(3) right
We need leftSize to know where to split! š
š Complexity Analysis
Time Complexity: O(n)
HashMap construction: O(n)
Process each element once
Recursive construction: O(n)
Visit each node once
O(1) lookup per node (thanks to HashMap)
Total: O(n) ā
Space Complexity: O(n)
HashMap: O(n)
Store all inorder indices
Recursion stack: O(h)
Best case: O(log n)
Worst case: O(n)
Total: O(n)
ā ļø Common Mistakes
Mistake 1: Wrong Preorder Partitioning
// ā WRONG - Incorrect left subtree range
root.left = build(preorder, preStart, preStart + leftSize, // WRONG!
inorder, inStart, rootIndex - 1);
// Problem: Includes one extra element!
// If leftSize = 1:
// Should take preorder[1 to 1] (1 element)
// This takes preorder[1 to 2] (2 elements!) ā
// ā CORRECT - Proper range
root.left = build(preorder, preStart + 1, preStart + leftSize, ā
inorder, inStart, rootIndex - 1);
Mistake 2: Not Using HashMap
// ā WRONG - Linear search each time
private int findRoot(int[] inorder, int val, int start, int end) {
for (int i = start; i <= end; i++) {
if (inorder[i] == val) return i;
}
return -1;
}
// Time: O(nĀ²) overall ā
// Each of n nodes does O(n) search
// ā CORRECT - HashMap for O(1) lookup
Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
// Time: O(n) overall ā
Mistake 3: Wrong Base Case
// ā WRONG - Checking array lengths
if (preorder.length == 0) return null; // WRONG!
// Problem: We pass indices, not subarrays!
// Length is always same, doesn't change!
// ā CORRECT - Check indices
if (preStart > preEnd) return null; ā
// OR
if (inStart > inEnd) return null; ā
Mistake 4: Forgetting to Skip Root in Preorder
// ā WRONG - Includes root in left subtree
root.left = build(preorder, preStart, preStart + leftSize, // Includes root!
inorder, inStart, rootIndex - 1);
// ā CORRECT - Skip root (preStart + 1)
root.left = build(preorder, preStart + 1, preStart + leftSize, ā
inorder, inStart, rootIndex - 1);
Mistake 5: Wrong leftSize Calculation
// ā WRONG - Forgets about inStart
int leftSize = rootIndex; // WRONG if inStart != 0!
// Example:
// inStart = 2, rootIndex = 3
// leftSize should be 1 (one element between 2 and 3)
// This calculates: 3 ā
// ā CORRECT - Subtract inStart
int leftSize = rootIndex - inStart; ā
šÆ Pattern Recognition - Array Reconstruction Problems
Core Pattern: Divide and Conquer with Properties
Template for reconstruction from traversals:
1. Identify root from one traversal
2. Use another traversal to partition
3. Calculate sizes for partitioning
4. Recursively build subtrees
5. Connect and return
Related Problems:
1. Construct Tree from Inorder and Postorder
Similar to this problem!
Difference: Postorder root is LAST element
Partition logic same, just different root position
2. Construct Tree from Preorder (BST)
Only need preorder for BST!
WHY? BST property gives us inorder (sorted)
Use value comparisons to partition
3. Serialize and Deserialize Binary Tree
Encode tree to string
Decode string to tree
Similar reconstruction logic
4. Verify Preorder Serialization
Check if string is valid tree
Use same traversal understanding
When to Use This Pattern:
ā Reconstruct tree from traversals
ā Two arrays with different orders
ā Need to identify structure
ā Divide and conquer applicable
ā HashMap for optimization
š Quick Revision Notes
šÆ Core Concept
Build tree from preorder and inorder arrays. Preorder gives root (first element), inorder partitions left/right (elements before/after root). Use HashMap for O(1) root lookup. Calculate leftSize to partition preorder correctly. Recursively build left and right subtrees with proper index ranges. Divide and conquer!
ā” Quick Implementation
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preorderStart = 0;
int preorderEnd = preorder.length - 1;
int inorderStart = 0;
int inorderEnd = inorder.length - 1;
HashMap<Integer, Integer> inorderMap = new HashMap<>();
for(int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return buildTree(preorderStart, preorderEnd, inorderStart, inorderEnd, inorderMap, preorder, inorder);
}
private TreeNode buildTree(int preorderStart, int preorderEnd, int inorderStart, int inorderEnd,
HashMap<Integer,Integer> inorderMap, int[] preorder, int[] inorder) {
// base case - boundary checks
if(preorderStart > preorderEnd || inorderStart > inorderEnd) {
return null; // this case should never exist and may exist for leaf nodes. Returns null.
}
// step 1: always start element of the preorder array is the root element.
// why preorderstart instead of 0? It will not be always 0 as we divide array more number of subarrays later in the future.
int rootElement = preorder[preorderStart];
// Get index of root element in inorder array.
// It is guaranteed that all elements are unique.
// Element before this rootElementIndex belong to LST and after this rootElementIndex belong to RST.
int rootElementIndex = inorderMap.get(rootElement);
// Step 2: Initialize root with root element and constrct LST and RST.
TreeNode root = new TreeNode(rootElement);
// Step 3: This is the ONLY GOTCHA of this whole problem. How much (size of LST) I have to take in preorder array is the main issue?
// This is not the issue with inorder array as root element index already decides that.
int leftSubtreeSize = rootElementIndex - inorderStart;
// Step 4: Construct LST with the remains of preorder and inorder arrays.
// All are intuitive if you put on paper except a little care on leftSubtreeSize.
root.left = buildTree(preorderStart + 1, preorderStart + leftSubtreeSize, inorderStart, rootElementIndex - 1, inorderMap, preorder, inorder);
// Step 5: Construct RST with the remains of preorder and inorder arrays.
// All are intuitive if you put on paper
root.right = buildTree(preorderStart + leftSubtreeSize + 1, preorderEnd, rootElementIndex + 1, inorderEnd, inorderMap, preorder, inorder);
return root;
}
public static void main(String[] args) {
Solution s = new Solution();
TreeNode res1 = s.buildTree(new int[] {3,9,20,15,7}, new int[] {9,3,15,20,7});
TreeNode.print(res1);
}
}
š Key Insights
Traversal Properties:
PREORDER (Root ā Left ā Right):
[Root, ...Left..., ...Right...]
ā
First element = ROOT!
INORDER (Left ā Root ā Right):
[...Left..., Root, ...Right...]
ā
Elements before root = LEFT
Elements after root = RIGHT
Together ā Unique tree! š
The Partitioning Magic:
Given root position in inorder:
leftSize = rootIndex - inStart
This tells us:
- How many elements in left subtree
- Where to split preorder:
Left: preorder[preStart+1 to preStart+leftSize]
Right: preorder[preStart+leftSize+1 to preEnd]
Without leftSize, can't partition preorder! šÆ
HashMap Optimization:
WITHOUT HashMap:
For each node: Linear search in inorder
Time: O(n) Ć O(n) = O(nĀ²) ā
WITH HashMap:
Precompute: O(n) once
Lookup: O(1) per node
Time: O(n) ā
Critical optimization! ā”
Index Range Pattern:
Always pass indices, not subarrays!
Advantages:
- No array copying: O(1) space
- Same arrays throughout
- Just track ranges
Ranges:
preorder: [preStart, preEnd]
inorder: [inStart, inEnd]
Base case: preStart > preEnd
šŖ Memory Aid
"Preorder gives ROOT (first element)!"
"Inorder splits LEFT/RIGHT (before/after root)!"
"leftSize = rootIndex - inStart!"
"HashMap for O(1) lookup!" āØ
ā ļø Don't Forget
- Preorder first = root (always!)
- Find root in inorder (splits tree!)
- Calculate leftSize (for partitioning!)
- Skip root in preorder (preStart + 1!)
- HashMap for O(1) (not O(n) search!)
- Pass indices not arrays (avoid copying!)
š Congratulations!
You've mastered tree reconstruction from traversals!
What You Learned:
ā
Traversal properties - What they encode
ā
Divide and conquer - Recursive partitioning
ā
HashMap optimization - O(nĀ²) ā O(n)
ā
Index arithmetic - Proper range calculations
ā
Tree construction - Building from arrays
ā
Pattern recognition - Similar problems
The Deep Understanding:
Traversals aren't just for printing!
They ENCODE the tree structure!
Preorder + Inorder ā Unique tree
Inorder + Postorder ā Unique tree
Preorder alone ā Not unique (need BST property)
Understanding traversals deeply! š§
Interview Mastery:
Interviewer: "Build tree from preorder and inorder"
Your approach:
"Preorder tells us the root (first element).
Inorder tells us left vs right split.
Algorithm:
1. Root = preorder[0]
2. Find root in inorder
3. Calculate leftSize for partitioning
4. Recursively build left and right
Optimization: HashMap for O(1) lookup
Time: O(n), Space: O(n)"
Shows deep understanding! šÆ
You've learned a fundamental reconstruction algorithm! šāØšÆ