Construct Binary Tree from Preorder and Inorder Traversal
Medium · Trees · Array · Hash Table · Divide and Conquer · Tree · Binary Tree
Problem
Two lists describe the same binary tree. preorder lists every node before its subtrees (node, left, right); inorder lists the left subtree, then the node, then the right subtree. All values are distinct. Rebuild the tree and return its root.
Neither list is enough alone — many trees share a preorder — but together they pin the tree down exactly. The first preorder value is the root, and finding it in inorder splits the remaining values into the left subtree’s and the right subtree’s.
The tree you return is graded by unrolling it with to_level. Trees here are at most 500 levels deep, so recursion is safe: LeetCode allows a 3,000-node chain, which is deeper than Python’s default recursion limit of 1,000.
The node type and two helpers are provided:
Examples
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,None,None,15,7]
3 is first in preorder, so it is the root. In inorder only 9 is to its left, and 15, 20, 7 are to its right. Of those, 20 comes first in preorder, so it roots the right subtree, with 15 and 7 as its children.
Input: preorder = [1,2,3], inorder = [3,2,1] Output: [1,2,None,3]
Every other value sits left of 1 in inorder, so 2 and 3 form its left subtree; the same happens again at 2. The result is a chain going left.
Constraints
- 1 <= len(preorder) <= 3000
- len(inorder) == len(preorder)
- -3000 <= preorder[i], inorder[i] <= 3000
- all values are distinct, and both lists describe the same tree
- the tree is at most 500 levels deep (LeetCode allows a 3,000-node chain; tightened so recursion fits in the browser)
Approaches
- Split with index() and slices — time O(n · h), O(n²) worst case, space O(n · h)
Related problems
Start free on Cariara · Coding problems · System design studio
