~20 minutes · Day 42 · preorder + inorder
Interview tree problems often give you a finished tree and ask for a property. This one is different: Construct Binary Tree from Preorder and Inorder Traversal gives you two traversal lists and asks you to rebuild the tree itself. The win is learning to use traversal order as structure, not just as output.
The first preorder value is the root, and its position in inorder splits everything into left and right subtrees — recurse with a hashmap for O(1) splits.
That sentence is the whole pattern. Preorder visits root before its subtrees. Inorder visits left subtree, then root, then right subtree. So preorder tells you which root comes next; inorder tells you which values belong left and right.
Preorder chooses the next root; inorder uses that root as the divider between the left and right subtree ranges.
The direct approach works like this: take the next preorder value as the root, then search for that value inside inorder to find the split point. If you do that search with inorder.index(root) at every recursive call, the repeated scan can cost O(n) per node. In the worst case, that becomes O(n²).
def build(preorder, inorder):
root_val = preorder[0]
mid = inorder.index(root_val) # linear scan each time
left = build(preorder[1:mid+1], inorder[:mid])
right = build(preorder[mid+1:], inorder[mid+1:])
There is a second hidden cost too: slicing creates new lists. The cleaner version keeps index boundaries and precomputes a dict from value to inorder index. Python dictionaries give average O(1) key lookup, so every split is found immediately (Python wiki: time complexity). The LeetCode version has unique values, so this map is unambiguous.
Use one moving pointer through preorder. Each recursive call owns an inorder range lo..hi. If the range is empty, there is no node. Otherwise, preorder gives the root, the map gives the split, and the two smaller ranges become the left and right subtrees.
def buildTree(preorder, inorder):
where = {v: i for i, v in enumerate(inorder)} # value -> inorder index
pre_i = 0 # next root in preorder
def build(lo, hi):
nonlocal pre_i
if lo > hi: return None # empty subtree
root_val = preorder[pre_i]; pre_i += 1 # root first
root = TreeNode(root_val)
mid = where[root_val] # O(1) split
root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)
return root
return build(0, len(inorder) - 1)The order of the two recursive calls matters. Because preorder is root, then left, then right, the left subtree must consume its roots before the right subtree starts.
The numbered nodes show why the recursive code must build the left subtree before it lets preorder move into the right subtree.
Construct Binary Tree from Inorder and Postorder Traversal is the same reconstruction idea with one key change. Postorder visits left, then right, then root, so the root is at the end instead of the beginning.
Before opening the reveal: predict the only two changes. Which end of postorder should you read from, and which subtree should you build first?
Read postorder from the end, because the last value is the root. Build the right subtree before the left subtree, because walking backward through postorder sees root, then right, then left. The inorder hashmap still does the same O(1) split.
| Approach | Time | Space |
|---|---|---|
| Brute force (search inorder for each root) | O(n²) | O(n) |
| Root split + hashmap | O(n) | O(n) |
The space is for the hashmap and the recursion stack. The speedup comes from refusing to rediscover the same inorder positions over and over.
1. What does the first preorder value identify?
2. What does the root's inorder position do?
3. Why avoid inorder.index(root_val) inside every recursive call?
index searches through the list. Repeating that search once per node can push the solution to O(n²) in a skewed tree.4. Which task is this pattern in disguise?
Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
For the encode step, write the invariant at the top of this page in your own words. Revision days test that sentence, not whether the code looked familiar for one night.
Watch NeetCode — Construct Binary Tree from Preorder and Inorder Traversal after your attempt, as the compare step. Find the exact sentence where his recursive split reasoning differs from yours.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.