Practice Construct Binary Tree from Preorder and Inorder Traversal
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
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.
Source: Construct Binary Tree from Preorder and Inorder Traversal on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
[3,9,20,null,null,15,7]
# Example 2
preorder = [-1], inorder = [-1]
[-1]
Constraints
How to solve Construct Binary Tree from Preorder and Inorder Traversal
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
The first element of preorder is the root of the current subtree, and its position in inorder splits that sequence into the left subtree (everything before) and the right subtree (everything after). The left part's size says how many following preorder elements belong to the left subtree.
Why brute force is not enough
At each root, scan inorder linearly for the split point and slice both arrays into fresh copies for the recursive calls. That is O(n^2) time and memory for a skewed tree of 3000 nodes.
Approach
- Build a hash map from each value to its inorder index; values are unique.
- Recursively build the subtree whose inorder values occupy a given index range, consuming preorder through one shared forward-moving cursor. Invariant: when a call begins, the cursor points at the root of exactly that subtree.
- If the range is empty, return nothing; otherwise take the value under the cursor as the root, look up its inorder index, and advance the cursor.
- Build the left child from the range before that index first, then the right child from the range after it; preorder lists the whole left subtree before the right.
- Return the root. No arrays are copied.
Walkthrough of Example 1
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → [3,9,20,null,null,15,7]
- Inorder positions: 9 at 0, 3 at 1, 15 at 2, 20 at 3, 7 at 4. For range 0 to 4 the cursor gives 3, at inorder index 1, so 3 is the root.
- Left range 0 to 0: the cursor gives 9 at index 0; its sub-ranges are empty, so 9 is a leaf and the left child of 3.
- Right range 2 to 4: the cursor gives 20 at index 3. Its left range 2 to 2 yields the leaf 15; its right range 4 to 4 yields the leaf 7.
- Preorder is fully consumed. The tree is 3 with children 9 and 20, where 20 has children 15 and 7; in level order, 3, 9, 20, null, null, 15, 7.
Time and space
Time O(n) · Space O(n). n is the number of nodes; the map is built once and each node costs a constant-time lookup, while the map plus the recursion stack take O(n) in the worst case.
Interview pitfalls
- Slicing arrays at every level, which turns a linear algorithm into a quadratic one.
- Building the right subtree before the left while sharing a preorder cursor; the cursor must consume nodes in root, left, right order.
- With explicit preorder indices instead of a cursor, miscomputing the right subtree's start: current start plus left subtree size plus one.
- Not anticipating a fully skewed 3000-node tree, where recursion depth may need an iterative rebuild.
Follow-up questions interviewers ask
- Reconstruct from inorder and postorder; which end of postorder supplies roots and which child is built first?
- Reconstruct from preorder and postorder alone; why is the tree not always unique?
Further reading on the technique: Tree traversal
Related LeetCode Problems
Practice more problems similar to Construct Binary Tree from Preorder and Inorder Traversal.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.