Construct BT from Preorder and Inorder
Rebuild the unique binary tree from its preorder and inorder traversals.
Open on LeetCode ↗Intuition
Preorder's first element is always the root. Find it in inorder: everything left of it is the left subtree, everything right the right subtree. Recurse with the matching slices. A value→index map makes each root lookup O(1).
Preorder hands you roots in order; inorder tells you where each root splits its subtree. The hash map from value to inorder index turns the "find the root" step from a linear scan into O(1), which is the difference between O(n²) and O(n).
Approach
Root from preorder, split from inorder
pre[0] = root; its inorder position k splits inorder into left (size k) and right parts.
Slice preorder to match
The next k preorder elements belong to the left subtree, the rest to the right — same sizes as the inorder split.
Index map + pointers
Precompute value → inorder index; pass array bounds instead of copying slices → O(n) total.
Solution & live demo
Common pitfalls
Searching the inorder array each time
mid = inorder.index(val)
idx = {v: i for i, v in enumerate(inorder)}
... idx[val]A linear search at every node makes the build O(n²), which times out on a skewed tree of 3,000 nodes. Precomputing positions once makes each lookup constant.
Passing the preorder index by value
def build(lo, hi, pre):
val = preorder[pre]
node.left = build(lo, mid - 1, pre + 1)self.pre = 0 ... val = preorder[self.pre]; self.pre += 1
The left subtree consumes an unknown number of preorder entries, so the right subtree's starting index isn't pre + 1 — it depends on how many nodes the left call used. A shared cursor advances correctly without that arithmetic.
Building the right subtree first
node.right = build(idx[val] + 1, hi) node.left = build(lo, idx[val] - 1)
node.left = build(lo, idx[val] - 1) node.right = build(idx[val] + 1, hi)
Preorder lays out root, then the entire left subtree, then the right. A shared cursor must consume them in that same order, so left has to be built first — the opposite of the postorder variant.
Edge cases
One side of every split is empty; recursion depth n.
Problem guarantees uniqueness — the split would be ambiguous otherwise.