44 / 75
Medium
Construct Binary Tree from Preorder and Inorder Traversal
#44treedfsarrayhash-tabledivide-and-conquer
Use preorder's first element as root, find it in inorder to split left/right subtrees recursively.
Example:
Input:
preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]Output:
Tree: [3,9,20,null,null,15,7]Common Mistakes:
- Not using HashMap to find root index in inorder (causes O(n²) time)
- Incorrect calculation of left/right subtree boundaries
- Not tracking preorder index properly across recursive calls
- Trying to use postorder logic for preorder
Notes:
Key insight: preorder gives root order, inorder splits left/right subtrees. Time O(n), Space O(n) with HashMap. Without HashMap: O(n²).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Use preorder's first element as root, find it in inorder to split left/right subtrees recursively.
Example:
Input:
preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]Output:
Tree: [3,9,20,null,null,15,7]Common Mistakes:
- Not using HashMap to find root index in inorder (causes O(n²) time)
- Incorrect calculation of left/right subtree boundaries
- Not tracking preorder index properly across recursive calls
- Trying to use postorder logic for preorder
Notes:
Key insight: preorder gives root order, inorder splits left/right subtrees. Time O(n), Space O(n) with HashMap. Without HashMap: O(n²).
44/75
Construct Binary Tree from Preorder and Inorder Traversal