Construct Binary Tree from Preorder and Inorder Traversal
You're given two integer arrays, preorder and inorder, that describe the same binary tree. preorder lists the nodes in the order root, then left subtree, then right subtree; inorder lists them as left subtree, then root, then right subtree. All values are distinct. Rebuild the tree and return its root. The output is shown in level order, with null marking a missing child.
Examples
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] returns [3,9,20,null,null,15,7]
preorder starts with 3, so 3 is the root. In inorder, only 9 sits left of 3, so 9 is the whole left subtree, while 15, 20 and 7 form the right subtree. Of those, 20 comes first in preorder, so it is that subtree's root with 15 on its left and 7 on its right.
preorder = [-1], inorder = [-1] returns [-1]
A single value makes a tree with just a root.
Constraints
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values.
- Each value of inorder also appears in preorder.
- preorder and inorder are valid traversals of the same tree.
Hints
Which array tells you the root right away, and which one tells you what belongs on each side of it?
Divide and conquer with recursion (depth-first): preorder[0] is the root, and its index in inorder splits the left and right subtrees. A hash map from value to inorder index makes each lookup O(1).
Keep an index into preorder. build(lo, hi) covers an inorder range: if lo > hi, return null. Take the next preorder value as the root, find its inorder index mid, build the left from (lo, mid - 1), then the right from (mid + 1, hi).
Drill This: Your Approach First
Approach
The first value in preorder is always the root, and its position in inorder splits the rest: values to its left form the left subtree, values to its right form the right subtree. Recurse on those inorder ranges while consuming preorder left to right (root, then the whole left subtree, then the right). A value-to-index map makes each split O(1). O(n) time, O(n) space for the map and recursion.
Time
O(n)
Space
O(n)
Pitfall
Solutions
class Solution {
private int preIdx;
private Map<Integer, Integer> inPos;
public TreeNode buildTree(int[] preorder, int[] inorder) {
preIdx = 0;
inPos = new HashMap<>();
for (int i = 0; i < inorder.length; i++) inPos.put(inorder[i], i);
return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int lo, int hi) {
if (lo > hi) return null;
int rootVal = preorder[preIdx++];
TreeNode root = new TreeNode(rootVal);
int mid = inPos.get(rootVal);
root.left = build(preorder, lo, mid - 1);
root.right = build(preorder, mid + 1, hi);
return root;
}
}from typing import List, Optional
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
in_pos = {val: i for i, val in enumerate(inorder)}
pre_idx = 0
def build(lo: int, hi: int) -> Optional[TreeNode]:
nonlocal pre_idx
if lo > hi:
return None
root_val = preorder[pre_idx]
pre_idx += 1
root = TreeNode(root_val)
mid = in_pos[root_val]
root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)
return root
return build(0, len(inorder) - 1)