Example 1
ready- Input
preorder = [ 3, 9, 20, 15, 7 ] inorder = [ 9, 3, 15, 20, 7 ]- Expected
[ 3, 9, 20, null, null, 15, 7 ]- Why
- 3 is the preorder root; inorder places 9 left and the 20 subtree right
Construct Tree from Preorder and Inorder
35 min · buildTree()mediumOpen in LeetCode #105 ↗
Two guest lists record the same tree in different orders. Put them together, and every left and right branch becomes recoverable.
You're given two arrays containing the same unique integer values:
- preorder traversal visits a node before its left and right subtrees.
- inorder traversal visits the left subtree, then the node, then the right subtree.
Reconstruct the binary tree and return its root. The judge serializes your returned tree
as a level-order array, using null for missing children, so it can compare the shape as
well as the values.
A few ground rules:
preorderandinorderalways describe the same tree.- Values are unique, so each root has one unambiguous position in
inorder. - Two empty arrays describe an empty tree; return
null, which serializes as[].
Constraints
0 <= preorder.length == inorder.length <= 10_000- All values are unique.
-2_147_483_648 <= preorder[i], inorder[i] <= 2_147_483_647preorderandinorderare consistent traversals of the same tree.
Hints
The first root is free
The first value in preorder must be the root. Find that value in inorder; what do the values on its left and right represent?
Measure the left subtree
If the root splits inorder after left_size values, the next left_size preorder
values belong to the left subtree. That gives both recursive ranges.
Stop searching for the split
Repeatedly scanning inorder can become quadratic on a one-sided tree. Build a map from value to inorder index once, then every split is an O(1) lookup.
Follow-up
Why does this reconstruction become ambiguous when values may repeat, and what extra information would you need to remove that ambiguity?
Visible cases
Examples
Example 2
ready- Input
preorder = [ -1 ] inorder = [ -1 ]- Expected
[ -1 ]- Why
- one value reconstructs one node
Example 3
ready- Input
preorder = [] inorder = []- Expected
[]- Why
- empty traversals reconstruct an empty tree
Interview signal
Asked at
AmazonGoogleBloomberg
Scan each in-order slice
Preorder reveals the root first. Locate that root inside the current inorder range: everything left of the split belongs to the left subtree, and everything right belongs to the right subtree. The left range's length tells you where the right subtree begins in preorder.
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> TreeNode | None:
if pre_left > pre_right:
return None
root_value = preorder[pre_left]
split = in_left
while inorder[split] != root_value:
split += 1
left_size = split - in_left
root = TreeNode(root_value)
root.left = build(
pre_left + 1,
pre_left + left_size,
in_left,
split - 1,
)
root.right = build(
pre_left + left_size + 1,
pre_right,
split + 1,
in_right,
)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)The recursion is correct, but a left-only tree puts each root at the far end of its
inorder range. The scans then cost n + (n - 1) + ... + 1.
Time O(n²) in the worst case. Space O(h) auxiliary space for recursion, excluding the returned tree.
Index map + ranges
The repeated work is finding a root's inorder position. Build one value → index map before the recursion. Every split then costs O(1); the range arithmetic stays unchanged.
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
inorder_index = {value: i for i, value in enumerate(inorder)}
def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> TreeNode | None:
if pre_left > pre_right:
return None
root_value = preorder[pre_left]
split = inorder_index[root_value]
left_size = split - in_left
root = TreeNode(root_value)
root.left = build(
pre_left + 1,
pre_left + left_size,
in_left,
split - 1,
)
root.right = build(
pre_left + left_size + 1,
pre_right,
split + 1,
in_right,
)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)Each value creates exactly one node. The preorder ranges decide which root comes next; the inorder ranges decide which side each remaining value belongs to.
Time O(n) — O(n) to build the map and O(1) work per node. Space O(n) for the map plus O(h) recursion, excluding the returned tree.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 3, 9, 20, null, null, 15, 7 ]
Run: visible + custom · Submit: full suite