Given two integer arrays preorder and inorder representing the preorder and inorder traversal of a binary tree with unique values, reconstruct and return that binary tree.
The first element of preorder is always the root of the (sub)tree currently being built.
Once the root is known, its position in inorder splits that segment into the left subtree's values (before it) and the right subtree's values (after it).
A hashmap from value to its index in inorder turns that split into an O(1) lookup; consuming preorder with a shared index pointer avoids costly list slicing.
Step-by-Step Analysis
Build a hashmap inorder_index mapping value → index in inorder.
Keep a pointer pre_idx starting at 0 into preorder.
Define build(left, right) over the current inorder segment; if left > right, return None.
Take root_val = preorder[pre_idx], advance pre_idx, create a TreeNode(root_val).
Look up mid = inorder_index[root_val]; recursively build the left subtree over inorder[left..mid-1] and the right subtree over inorder[mid+1..right], attach both, and return root.
Complexity
Time: O(n) — Space: O(n)
Code
def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
inorder_index = {val: i for i, val in enumerate(inorder)}
pre_idx = 0
def build(left: int, right: int) -> TreeNode | None:
nonlocal pre_idx
if left > right:
return None
root_val = preorder[pre_idx]
pre_idx += 1
root = TreeNode(root_val)
mid = inorder_index[root_val]
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(inorder) - 1)
Code Explanation
How the solution above works, piece by piece.
inorder_index maps value → position in inorder, so finding the split point is O(1).
pre_idx walks through preorder: each value taken is the root of the subtree currently being built.
build(left, right) constructs the subtree whose values occupy inorder[left..right]; an empty range returns None.
mid is the root's inorder position: build the left part left..mid−1 first, then the right part. The left subtree must be built first because preorder lists it first.
O(n) time and O(n) space for the map.
Visual Walkthrough
Running it on preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]:
Preorder lists a root before its subtrees, so the next preorder value is always the root of the subtree being built. That value's position in inorder says which values go left (before it) and right (after it). Repeating this builds the tree on the right.