• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• All values in the tree are unique
• preorder and inorder are guaranteed to be valid traversals of the same tree

Until now we have been reading trees. This problem runs the machine backwards: given two readings, rebuild the tree that produced them. The first thing to settle is why two readings are needed at all.

Take the pre-order list [1, 2]. Pre-order visits the node, then the left subtree, then the right, so 1 is certainly the root and 2 is certainly its only child — but on which side? A tree with 2 as a left child gives pre-order [1, 2]. A tree with 2 as a right child gives pre-order [1, 2] as well. The two shapes are genuinely indistinguishable, so no algorithm can recover the tree from pre-order alone.

In-order alone fails too, and worse: [2, 1] is consistent with 2 being 1's left child, or with 1 being 2's right child, and with many larger shapes besides. Neither reading is enough on its own.

Now put them together. Pre-order says which node is the root. In-order says, for a known root, which values fall to its left and which to its right — because in-order visits the entire left subtree, then the node, then the entire right subtree, so the root's position in that list is precisely the boundary between the two sides. Between them the ambiguity vanishes: [1,2] with in-order [2,1] must be a left child, and with in-order [1,2] must be a right child.

State the division of labour plainly, because it is the whole solution:

And once the split is known, the sizes are known. If the in-order split says the left subtree contains k values, then in the pre-order segment — which lists the root, then all of the left subtree, then all of the right — the k entries immediately after the root are exactly the left subtree's, and the remainder is the right subtree's. Both arrays can now be cut into matching pieces, and each pair of pieces is a smaller instance of the identical problem. That is the recursion.

Building the parent before its children is what lets us hand back a finished node with both links attached, so the construction runs top-down — pre-order in shape as well as in name.

pos = {v: i for i, v in enumerate(inorder)}   # value -> its index in inorder, built once

def build(pre_lo, pre_hi, in_lo, in_hi):      # both ranges inclusive
    if pre_lo > pre_hi:
        return None                            # an empty segment is an empty subtree
    root_val = preorder[pre_lo]                # pre-order: the root comes first
    root = Node(root_val)
    mid = pos[root_val]                        # in-order: where the split falls
    left_size = mid - in_lo                    # how many values sit on the left
    root.left  = build(pre_lo + 1, pre_lo + left_size, in_lo, mid - 1)
    root.right = build(pre_lo + left_size + 1, pre_hi, mid + 1, in_hi)
    return root

return build(0, len(preorder) - 1, 0, len(inorder) - 1)

Locating the root inside the in-order segment by scanning costs up to O(N) per node, and with N nodes that is O(N²) — 9 million steps at the 3000-node limit, and the scan repeats work at every level. But the in-order array never changes, and every value is unique, so each value's position can be recorded once, up front, in a hash map from value to index. Lookups then take constant time regardless of the array's size, and the total drops to O(N).

This is the same trade made in Two Sum: spend O(N) memory to remember positions, and a repeated linear search collapses into a single constant-time question. The uniqueness guarantee is what licenses it — with duplicate values a single map entry could not identify the right occurrence, and indeed the input would no longer determine one tree.

Notice how the pre-order slice [20, 15, 7] is not itself in any useful order for the split — 15 and 7 are neighbours there with no marker between them. It was the in-order slice that said "one value goes left," and only then did the pre-order slice know where to cut.

Every node is created exactly once, and with the map each creation is constant work: O(N) time. Space is O(N) for the map plus O(H) for the recursion, so O(N) overall. Without the map it degrades to O(N²), which on a chain-shaped tree is the worst case.

The reusable idea is divide and conquer keyed on a pivot: identify the element that splits the problem, use a second source of information to find where the split falls, and recurse on the two halves with carefully synchronised boundaries. It is the same skeleton as quicksort's partition and as binary search's midpoint, and here it is applied to reconstruction rather than sorting. The very next problem swaps pre-order for post-order — where the root is the last element rather than the first, so the recursion builds the right subtree before the left — and Serialize and Deserialize goes further, showing that with null markers included a single traversal becomes sufficient after all.