Rebuild From Two Walks
Problem
You are handed the values of a binary tree in two orders: the walk that visits a node before its subtrees, and the walk that visits the left subtree, then the node, then the right subtree. All values are distinct. Reconstruct the tree those two walks came from and return its root.
Examples
Input: before = [3, 9, 20, 15, 7], middle = [9, 3, 15, 20, 7]
Output: 3 with left child 9 and right child 20, whose children are 15 and 7Input: before = [1, 2], middle = [2, 1]
Output: 1 with a single left child 2
Why: the middle walk is what reveals the child hangs on the leftInput: before = [], middle = []
Output: empty
Why: edge case, two empty walks describe an empty treeHints
0 / 3
Each walk alone is ambiguous, but together they pin the tree down. Ask what the very first value of the before-walk tells you.
Once you know which value is the root, the middle walk splits into everything left of it and everything right of it, and those two pieces are exactly the two subtrees.
Find each value's position in the middle walk once, up front, so the split is not a search. Then consume the before-walk from left to right: take the next value as the current root, build its left subtree from the middle-walk slice before that value, and its right subtree from the slice after it. Building the left side first is what keeps the before-walk in step.
Solution
The first unconsumed value of the before-walk is always the root of the subtree being built, and its position in the middle walk splits the remaining values into the left and right subtrees. Precomputing value-to-position in a map turns that split into a constant-time lookup instead of a scan, which is the difference between quadratic and linear. The before-walk is consumed through a single cursor, and the left subtree must be built before the right one so the cursor arrives at the correct value each time. Time is O(n) and space is O(n) for the map and the call stack.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def show(n): return "." if n is None else "(%s %s %s)" % (n.val, show(n.left), show(n.right))
def rebuild(before, middle):
place = {v: i for i, v in enumerate(middle)} # value -> slot in the middle walk
nxt = iter(before)
def build(lo, hi): # the subtree covering middle[lo..hi]
if lo > hi:
return None
node = T(next(nxt)) # the before-walk names each root first
node.left = build(lo, place[node.val] - 1) # left first, to stay in step
node.right = build(place[node.val] + 1, hi)
return node
return build(0, len(middle) - 1)
print(show(rebuild([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]))) # -> (3 (9 . .) (20 (15 . .) (7 . .)))
print(show(rebuild([1, 2], [2, 1]))) # -> (1 (2 . .) .)
print(show(rebuild([], []))) # -> .Stuck on the idea rather than the code? Rebuild From Traversals covers it.