Construct BT from Preorder and Inorder
Rebuild the unique binary tree from its preorder and inorder traversals.
Open on LeetCode ↗02
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).
03
Approach
1
Root from preorder, split from inorder
pre[0] = root; its inorder position k splits inorder into left (size k) and right parts.
2
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.
3
Index map + pointers
Precompute value → inorder index; pass array bounds instead of copying slices → O(n) total.
04
Solution & live demo
python
▶1class Solution:
▶2 def buildTree(self, preorder, inorder):
▶3 idx = {v: i for i, v in enumerate(inorder)}
▶4 self.pre = 0
▶5 def build(lo, hi): # inorder bounds
▶6 if lo > hi: return None
▶7 val = preorder[self.pre]; self.pre += 1
▶8 node = TreeNode(val)
▶9 node.left = build(lo, idx[val] - 1)
▶10 node.right = build(idx[val] + 1, hi)
▶11 return node
▶12 return build(0, len(inorder) - 1)
05
Edge cases
Skewed tree
One side of every split is empty; recursion depth n.
Duplicate values
Problem guarantees uniqueness — the split would be ambiguous otherwise.
06
Complexity
Time
O(n)
Space
O(n)
Hash map + single preorder pointer.