Construct Binary Tree from Preorder and Inorder Traversal

Medium· Divide and Conquer· Hash Map

Problem

You are given the preorder and inorder traversals of a binary tree whose values are all distinct. Rebuild the tree and return its root.

Examples

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Constraints

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• All values are unique

Hints & approach

Hint 1

The first element of preorder is always the root.

Hint 2

Find that root in inorder: everything to its left is the left subtree, everything to its right is the right subtree.

Hint 3

Use a hash map from value to inorder index so each split is O(1).

Approachtry the hints first

Precompute a map from value to its index in inorder. Recurse over an inorder range [lo, hi] while consuming preorder with a shared pointer: take the next preorder value as the root, look up its inorder index m, build the left subtree from [lo, m - 1] and then the right subtree from [m + 1, hi]. Building left before right matches preorder, so the pointer always lands on the correct next root.

Time O(n) · Space O(n)

← PreviousLowest Common Ancestor of a Binary Tree Next →Binary Tree Maximum Path Sum