Reconstruct a binary tree from its in-order and pre-order traversals (all values distinct) and return the root.
buildTreeInPre(inorder, preorder)
Input format: inorder | preorder. Output the tree in level-order form (x for
missing children).
inorder=9 3 15 20 7, preorder=3 9 20 15 7 // → 3 9 20 x x 15 7
inorder=1, preorder=1 // → 1
Like the in-order/post-order version, this works because in-order and pre-order each supply what the other lacks. In-order tells you which values fall left versus right of a root, not which value is the root. Pre-order tells you the root immediately, not where the split occurs. Together they pin down the tree's shape.
Pre-order visits node, left-subtree, right-subtree — the node comes first. So the first value of any pre-order sequence for a subtree is that subtree's root; for the whole tree, the first value overall is the root.
Locate the root's value in the in-order sequence. Since in-order visits left, node, right, everything before that position is the left subtree, everything after is the right — the same idea as the post-order version, approached from the opposite end.
Work over a shrinking in-order window (lo/hi), with a pointer into pre-order pointing at the next unconsumed value from the front. At each call: the current first unconsumed pre-order value is this subtree's root; find its split point in the in-order window, then recurse. Since pre-order is node, then left, then right, the value right after the root belongs to the left subtree — so build the left subtree first, then the right, consuming pre-order front-to-back correctly. lo exceeding hi means no subtree here.
Pre-order exposes its root at the front, consumed left-to-right, building left-before-right. Post-order exposes its root at the back, consumed right-to-left, building right-before-left. Spotting which end reveals the root, and consuming from that matching end, is the general strategy for this whole family of problems.
A value-to-index map over in-order makes each split an O(1) lookup instead of a linear scan — O(n) time overall, O(n) space for the map and the tree.
def build_tree_in_pre(inorder, preorder):
index_of = {v: i for i, v in enumerate(inorder)}
pre_idx = 0
def build(lo, hi):
nonlocal pre_idx
if lo > hi:
return None
val = preorder[pre_idx]
pre_idx += 1
node = TreeNode(val)
mid = index_of[val]
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(inorder) - 1)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.