Binary TreesProblem 20 of 35
Construct Binary tree from Inorder and preorder traversal
Problem Statement
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Example:
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
Output:
3
/ \
9 20
/ \
15 7
- Preorder: Root, Left, Right → 3 is root
- In inorder, elements left of 3 (i.e., 9) form left subtree
- Elements right of 3 (i.e., 15, 20, 7) form right subtree
Approach 1: Brute Force (Linear Search for Root)
Intuition
In preorder traversal, the first element is always the root. Find this root in inorder traversal - elements to its left form the left subtree, elements to its right form the right subtree. Recursively build subtrees.
Algorithm
- First element of preorder is the root
- Search for root in inorder array (linear search)
- Elements before root index in inorder = left subtree
- Elements after root index in inorder = right subtree
- Recursively construct left and right subtrees
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int preIndex = 0;
private int search(int[] inorder, int start, int end, int val) {
for (int i = start; i <= end; i++) {
if (inorder[i] == val) return i;
}
return -1;
}
private TreeNode buildTreeHelper(int[] preorder, int[] inorder,
int inStart, int inEnd) {
if (inStart > inEnd) return null;
// Pick current node from preorder
int rootVal = preorder[preIndex++];
TreeNode root = new TreeNode(rootVal);
// If this node has no children
if (inStart == inEnd) return root;
// Find index of root in inorder
int inIndex = search(inorder, inStart, inEnd, rootVal);
// Build left and right subtrees
root.left = buildTreeHelper(preorder, inorder, inStart, inIndex - 1);
root.right = buildTreeHelper(preorder, inorder, inIndex + 1, inEnd);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
preIndex = 0;
return buildTreeHelper(preorder, inorder, 0, inorder.length - 1);
}
}Complexity Analysis
- Time Complexity: O(n^2) - For each node, we do linear search in inorder array
- Space Complexity: O(n) - Recursion stack for skewed tree
Approach 2: Optimal (HashMap for O(1) Root Lookup)
Intuition
The bottleneck in the brute force approach is the linear search to find root index in inorder array. Use a HashMap to store value-to-index mapping for O(1) lookup.
Algorithm
- Build a HashMap mapping each value to its index in inorder array
- Use preorder index to pick root (increment after each use)
- Look up root's position in inorder using HashMap
- Recursively build left and right subtrees
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int preIndex = 0;
private Map<Integer, Integer> inorderMap = new HashMap<>();
private TreeNode buildTreeHelper(int[] preorder, int inStart, int inEnd) {
if (inStart > inEnd) return null;
// Pick current node from preorder
int rootVal = preorder[preIndex++];
TreeNode root = new TreeNode(rootVal);
// If this node has no children
if (inStart == inEnd) return root;
// Find index of root in inorder using map
int inIndex = inorderMap.get(rootVal);
// Build left and right subtrees
root.left = buildTreeHelper(preorder, inStart, inIndex - 1);
root.right = buildTreeHelper(preorder, inIndex + 1, inEnd);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
preIndex = 0;
inorderMap.clear();
// Build hashmap for O(1) lookup
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return buildTreeHelper(preorder, 0, inorder.length - 1);
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is processed once, HashMap lookup is O(1)
- Space Complexity: O(n) - HashMap storage + recursion stack
Key Takeaways
- Preorder first element = root - This is the key insight
- Inorder divides tree - Left of root = left subtree, Right of root = right subtree
- HashMap optimization - Converts O(n) search to O(1) lookup
- Same approach works for postorder + inorder - Just traverse postorder from right to left
- Cannot construct unique tree from preorder + postorder - Need inorder for unique reconstruction