Construct Binary Tree from Preorder and Inorder Traversal
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
