Language Selection
Choose your preferred programming language
Showing: Python
Construct Binary Tree from Preorder and Inorder 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.
Examples
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Explanation:
3
/ \
9 20
/ \
15 7
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Constraints
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorderandinorderconsist of unique values- Each value of
inorderalso appears inpreorder preorderis guaranteed to be the preorder traversal of the treeinorderis guaranteed to be the inorder traversal of the tree
Approach 1: Recursive with Hash Map (Optimal)
Algorithm
Use the property that the first element in preorder is always the root, and use inorder to determine left and right subtrees.
Steps:
- Create a hash map to store inorder indices for O(1) lookup
- Use preorder to get the root
- Find root position in inorder to split into left and right subtrees
- Recursively construct left and right subtrees
Implementation
Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
"""
Construct binary tree from preorder and inorder traversal
Time: O(n)
Space: O(n)
"""
if not preorder or not inorder:
return None
# Create hash map for O(1) lookup
inorder_map = {val: idx for idx, val in enumerate(inorder)}
def build(pre_start, pre_end, in_start, in_end):
if pre_start > pre_end:
return None
# Root is always first element in preorder
root_val = preorder[pre_start]
root = TreeNode(root_val)
# Find root position in inorder
root_idx = inorder_map[root_val]
# Calculate sizes of left and right subtrees
left_size = root_idx - in_start
# Recursively build left and right subtrees
root.left = build(pre_start + 1, pre_start + left_size, in_start, root_idx - 1)
root.right = build(pre_start + left_size + 1, pre_end, root_idx + 1, in_end)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)
Java:
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;
}
}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0) {
return null;
}
// Create hash map for O(1) lookup
Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(preorder, inorder, inorderMap, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] inorder, Map<Integer, Integer> inorderMap,
int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
// Root is always first element in preorder
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// Find root position in inorder
int rootIdx = inorderMap.get(rootVal);
// Calculate size of left subtree
int leftSize = rootIdx - inStart;
// Recursively build left and right subtrees
root.left = build(preorder, inorder, inorderMap,
preStart + 1, preStart + leftSize,
inStart, rootIdx - 1);
root.right = build(preorder, inorder, inorderMap,
preStart + leftSize + 1, preEnd,
rootIdx + 1, inEnd);
return root;
}
}
Go:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 || len(inorder) == 0 {
return nil
}
// Create hash map for O(1) lookup
inorderMap := make(map[int]int)
for i, val := range inorder {
inorderMap[val] = i
}
return build(preorder, inorder, inorderMap, 0, len(preorder)-1, 0, len(inorder)-1)
}
func build(preorder, inorder []int, inorderMap map[int]int, preStart, preEnd, inStart, inEnd int) *TreeNode {
if preStart > preEnd {
return nil
}
// Root is always first element in preorder
rootVal := preorder[preStart]
root := &TreeNode{Val: rootVal}
// Find root position in inorder
rootIdx := inorderMap[rootVal]
// Calculate size of left subtree
leftSize := rootIdx - inStart
// Recursively build left and right subtrees
root.Left = build(preorder, inorder, inorderMap,
preStart+1, preStart+leftSize,
inStart, rootIdx-1)
root.Right = build(preorder, inorder, inorderMap,
preStart+leftSize+1, preEnd,
rootIdx+1, inEnd)
return root
}
JavaScript:
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
}
function buildTree(preorder, inorder) {
if (!preorder || !inorder || preorder.length === 0) {
return null;
}
// Create hash map for O(1) lookup
const inorderMap = {};
for (let i = 0; i < inorder.length; i++) {
inorderMap[inorder[i]] = i;
}
function build(preStart, preEnd, inStart, inEnd) {
if (preStart > preEnd) {
return null;
}
// Root is always first element in preorder
const rootVal = preorder[preStart];
const root = new TreeNode(rootVal);
// Find root position in inorder
const rootIdx = inorderMap[rootVal];
// Calculate size of left subtree
const leftSize = rootIdx - inStart;
// Recursively build left and right subtrees
root.left = build(preStart + 1, preStart + leftSize, inStart, rootIdx - 1);
root.right = build(preStart + leftSize + 1, preEnd, rootIdx + 1, inEnd);
return root;
}
return build(0, preorder.length - 1, 0, inorder.length - 1);
}
C#:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode BuildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.Length == 0) {
return null;
}
// Create hash map for O(1) lookup
Dictionary<int, int> inorderMap = new Dictionary<int, int>();
for (int i = 0; i < inorder.Length; i++) {
inorderMap[inorder[i]] = i;
}
return Build(preorder, inorder, inorderMap, 0, preorder.Length - 1, 0, inorder.Length - 1);
}
private TreeNode Build(int[] preorder, int[] inorder, Dictionary<int, int> inorderMap,
int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
// Root is always first element in preorder
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// Find root position in inorder
int rootIdx = inorderMap[rootVal];
// Calculate size of left subtree
int leftSize = rootIdx - inStart;
// Recursively build left and right subtrees
root.left = Build(preorder, inorder, inorderMap,
preStart + 1, preStart + leftSize,
inStart, rootIdx - 1);
root.right = Build(preorder, inorder, inorderMap,
preStart + leftSize + 1, preEnd,
rootIdx + 1, inEnd);
return root;
}
}
Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - Hash map and recursion stack
Key Insights
- Root Identification: First element in preorder is always the root
- Subtree Splitting: Use inorder to determine left and right subtrees
- Hash Map Optimization: Use hash map for O(1) root position lookup
- Array Slicing: Split arrays based on subtree sizes
- Recursive Construction: Build left and right subtrees recursively
Edge Cases
- Empty Arrays: Return null
- Single Node: Return root node
- Left Skewed: Only left subtree
- Right Skewed: Only right subtree
- Complete Tree: Both subtrees present
Follow-up Questions
- Postorder + Inorder: How would you construct from postorder and inorder?
- Preorder + Postorder: Can you construct from preorder and postorder?
- Level Order: How would you construct from level order traversal?
- Validation: How would you validate the constructed tree?
- Serialization: How would you serialize the tree back to arrays?
Common Mistakes
- Index Confusion: Wrong array slicing or index calculations
- Root Position: Not finding correct root position in inorder
- Subtree Sizes: Incorrect calculation of left/right subtree sizes
- Base Case: Not handling empty arrays properly
- Array Bounds: Index out of bounds errors
Interview Tips
- Clarify Requirements: Ask about unique values and array lengths
- Discuss Approaches: Mention both hash map and linear search approaches
- Handle Edge Cases: Discuss empty arrays and single node scenarios
- Explain Algorithm: Walk through the root identification and splitting process
- Consider Optimizations: Discuss time-space tradeoffs