#105
Construct Binary Tree from Preorder and Inorder Traversal
Medium Divide by root position
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rebuild a binary tree (with unique values) from its preorder and inorder traversals.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rebuild the tree from two traversals.
Why this works: preorder gives the root first; in inorder everything left of the root is the left subtree.
Example: pre [3, 9, 20, 15, 7], in [9, 3, 15, 20, 7]
root 3; left {9}; right {15, 20, 7}next root 20 → left 15, right 7
✦Hints open one at a time
The first preorder value is the root.
In inorder, everything left of the root is the left subtree.
Store inorder positions in a HashMap for O(1) lookup.
↗Approach
Keep a pointer into preorder. build(lo, hi) over the inorder range: take the next preorder value as the root, find its inorder index m, build left from (lo, m − 1) then right from (m + 1, hi).
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
private int pre = 0;
private int[] preorder;
private final Map<Integer, Integer> pos = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return build(0, inorder.length - 1);
}
private TreeNode build(int lo, int hi) {
if (lo > hi) return null;
TreeNode root = new TreeNode(preorder[pre++]);
int m = pos.get(root.val);
root.left = build(lo, m - 1); // left first: matches preorder
root.right = build(m + 1, hi);
return root;
}
}!Common mistake
Building the right subtree before the left — preorder lists the left subtree first.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon