LC 105 · Medium · Divide and conquer · split by the root
Construct Binary Tree from Preorder and Inorder
Two traversal orders, and a tree to rebuild from them.
Recognise it
Before any code, what in the question tells you this is the pattern?
You are handed two traversal orders and asked to rebuild the tree. The general shape is that one traversal tells you the root and the other tells you how the rest splits.
The brute force
Always have this one ready. It is the honest starting point, and it is what the real solution improves on.
Take the first value of preorder as the root, scan inorder to find it, split inorder into the left and right halves, split preorder to match, and recurse on the four slices.
O(n squared) time in the worst case, plus O(n squared) total space if the slices are copies.
The idea is exactly right and the implementation is what costs you. Scanning inorder at every node is linear work per node, which on a skewed tree makes the whole thing quadratic. Copying array slices at every level compounds it. Both problems have the same fix: stop moving data around and pass indices instead.
The approach
The idea in plain language, before it becomes syntax.
Preorder visits the root before anything else, so its first unused value is always the root of whatever subtree you are currently building. That gives you the node.
Inorder visits the entire left subtree, then the root, then the entire right subtree. So once you know which value is the root, its position in inorder tells you exactly how many nodes fall on each side. That gives you the split.
Put those together and you never need to slice anything. Keep one shared cursor into preorder that advances once per node created, and pass a pair of inorder bounds to say which region you are building. Replace the scan with a value-to-index map built once at the start, and every node becomes constant work.
The algorithm
The same idea again, as steps you could follow with a pencil.
The solution
Now the code, and why each decision in it is the way it is.
def buildTree(preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)} # one lookup table, not a scan
i = 0
def go(lo, hi):
nonlocal i
if lo > hi:
return None
val = preorder[i]; i += 1 # advances exactly once per node
node = TreeNode(val)
node.left = go(lo, pos[val] - 1) # left first: preorder demands it
node.right = go(pos[val] + 1, hi)
return node
return go(0, len(inorder) - 1)The cursor must be shared across the whole recursion, not passed by value. Each node consumes exactly one preorder value, and the left subtree must consume all of its values before the right subtree starts. In Python that means <code>nonlocal</code>, and in Java a field.
Recursing left before right is therefore not a style choice, it is load-bearing. Swap the two lines and the cursor hands the left subtree values to the right one, and every node after the first is wrong.
The map turns this from quadratic to linear and costs O(n) space. That trade is the entire difference between the brute force and the real solution, and it is the kind of trade worth naming explicitly in an interview.
Uniqueness of values is assumed. With duplicates the position of the root in inorder is ambiguous and the tree cannot be reconstructed, which is a good clarifying question to ask before writing anything.
Where people slip
- Build a value to index map for inorder once, up front. Searching it linearly inside the recursion turns O(n) into O(n2).
- The preorder cursor is shared across the whole recursion and must advance exactly once per node. Passing it by value, or resetting it per call, silently builds the wrong tree.
- Recurse left before right. Preorder consumes the entire left subtree before the right one, so swapping the order corrupts every node after the first.
- This assumes values are unique. With duplicates the position in inorder is ambiguous and the problem is not solvable as stated.
Your notes
What tripped you up here? Write it in your own words.