Approach Summary
Preorder[0] is always the root. Find its index in inorder to split left/right subtrees. Recurse with slices.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Hash Map Inorder Lookups and Index Boundaries (Optimal) | O(n) | O(n) | Map inorder values to indices, partitioning left/right subtrees in O(1) lookup per node. |
| 2 Approach 2: Divide and Conquer with Linear Inorder Search (Baseline) | O(n²) | O(n) | Finds root in inorder array via linear scan at each recursion level, trading hash map space for O(n²) worst-case time. |
Step 1: Baseline
Approach 1: Hash Map Inorder Lookups and Index Boundaries (Optimal)
Time: O(n)
Space: O(n)
Because all tree node values are distinct, storing inorder indices in a hash map allows looking up the boundary between left and right subtrees in O(1) time, avoiding quadratic array slicing.
Approach 1: Hash Map Inorder Lookups and Index Boundaries (Optimal) Implementation
Approach 1: Hash Map Inorder Lookups and Index Boundaries (Optimal)
class Solution {
private TreeNode h(int[] pre, int ps, int pe, int[] in, int is, int ie, Map<Integer, Integer> m) {
if (ps > pe || is > ie) return null;
int val = pre[ps];
TreeNode root = new TreeNode(val);
int idx = m.get(val), sz = idx - is;
root.left = h(pre, ps + 1, ps + sz, in, is, idx - 1, m);
root.right = h(pre, ps + sz + 1, pe, in, idx + 1, ie, m);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < inorder.length; i++) m.put(inorder[i], i);
return h(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, m);
}
}class Solution {
public:
TreeNode* h(vector<int>& pre, int ps, int pe, vector<int>& in, int is, int ie, unordered_map<int, int>& m) {
if (ps > pe || is > ie) return NULL;
int val = pre[ps];
TreeNode* root = new TreeNode(val);
int idx = m[val], sz = idx - is;
root->left = h(pre, ps + 1, ps + sz, in, is, idx - 1, m);
root->right = h(pre, ps + sz + 1, pe, in, idx + 1, ie, m);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> m;
for (int i = 0; i < inorder.size(); i++) m[inorder[i]] = i;
return h(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, m);
}
};class Solution:
def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
m = {v: i for i, v in enumerate(inorder)}
def helper(p_s, p_e, i_s, i_e):
if p_s > p_e or i_s > i_e: return None
val = preorder[p_s]
root = TreeNode(val)
idx = m[val]
sz = idx - i_s
root.left = helper(p_s + 1, p_s + sz, i_s, idx - 1)
root.right = helper(p_s + sz + 1, p_e, idx + 1, i_e)
return root
return helper(0, len(preorder) - 1, 0, len(inorder) - 1)function buildTree(preorder, inorder) {
const m = new Map();
inorder.forEach((v, i) => m.set(v, i));
function h(ps, pe, is, ie) {
if (ps > pe || is > ie) return null;
const val = preorder[ps], root = new TreeNode(val);
const idx = m.get(val), sz = idx - is;
root.left = h(ps + 1, ps + sz, is, idx - 1);
root.right = h(ps + sz + 1, pe, idx + 1, ie);
return root;
}
return h(0, preorder.length - 1, 0, inorder.length - 1);
} Step 2: Most Optimized
Approach 2: Divide and Conquer with Linear Inorder Search (Baseline)
Time: O(n²)
Space: O(n)
Scans inorder array linearly to find root value index. Left of index forms left subtree, right forms right subtree. Space overhead is minimized but runtime becomes quadratic on skewed trees.
Approach 2: Divide and Conquer with Linear Inorder Search (Baseline) Implementation
Approach 2: Divide and Conquer with Linear Inorder Search (Baseline)
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
int val = preorder[0];
TreeNode root = new TreeNode(val);
int idx = 0;
while (inorder[idx] != val) idx++;
int[] leftPre = Arrays.copyOfRange(preorder, 1, 1 + idx);
int[] leftIn = Arrays.copyOfRange(inorder, 0, idx);
int[] rightPre = Arrays.copyOfRange(preorder, 1 + idx, preorder.length);
int[] rightIn = Arrays.copyOfRange(inorder, idx + 1, inorder.length);
root.left = buildTree(leftPre, leftIn);
root.right = buildTree(rightPre, rightIn);
return root;
}
}class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) return NULL;
int val = preorder[0];
TreeNode* root = new TreeNode(val);
auto it = find(inorder.begin(), inorder.end(), val);
int idx = distance(inorder.begin(), it);
vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + idx);
vector<int> leftIn(inorder.begin(), inorder.begin() + idx);
vector<int> rightPre(preorder.begin() + 1 + idx, preorder.end());
vector<int> rightIn(inorder.begin() + idx + 1, inorder.end());
root->left = buildTree(leftPre, leftIn);
root->right = buildTree(rightPre, rightIn);
return root;
}
};class Solution:
def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
if not preorder or not inorder: return None
val = preorder[0]
root = TreeNode(val)
idx = inorder.index(val)
root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])
root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])
return rootfunction buildTree(preorder, inorder) {
if (!preorder.length || !inorder.length) return null;
const val = preorder[0];
const root = new TreeNode(val);
const idx = inorder.indexOf(val);
root.left = buildTree(preorder.slice(1, 1 + idx), inorder.slice(0, idx));
root.right = buildTree(preorder.slice(1 + idx), inorder.slice(idx + 1));
return root;
}Edge Cases to Watch
- Single node tree (preorder = [1], inorder = [1]; returns node(1))
- Left-skewed tree
- Right-skewed tree
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- Preorder root + inorder split → two subtrees
- Use HashMap for O(1) inorder index lookup
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Hash Table Divide and Conquer Tree Binary Tree
Frequently Asked Questions
What is the optimal time and space complexity for Construct Binary Tree from Preorder and Inorder Traversal?
The optimal solution for Construct Binary Tree from Preorder and Inorder Traversal achieves O(n) runtime complexity and requires O(n) auxiliary space. Time complexity is O(n) because building the hash map takes O(n) and each of the n nodes is constructed in O(1) time. Space complexity is O(n) to store the hash map and recursion call stack.
How do I identify that Construct Binary Tree from Preorder and Inorder Traversal requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: Preorder root + inorder split → two subtrees; Use HashMap for O(1) inorder index lookup. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Construct Binary Tree from Preorder and Inorder Traversal?
Essential edge cases to verify include: Single node tree (preorder = [1], inorder = [1]; returns node(1)); Left-skewed tree; Right-skewed tree. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Construct Binary Tree from Preorder and Inorder Traversal?
Construct Binary Tree from Preorder and Inorder Traversal is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Google.