Binary Tree Reconstruction

Description

Reconstruction rebuilds a binary tree from two of its traversals. Preorder (or postorder) says which node is the root of each subtree. Inorder says where that root splits its subtree into left and right. Walk one sequence with a cursor, find each root's position in the other with a hash map, and recurse on the two sides: O(n) for the whole tree.

We'll go from simple to more technical:

1. The pattern: preorder + inorder, a shared cursor and an index map.
2. A second flavor: inorder + postorder, walking the cursor backwards.
3. Where rebuilding a structure from linear views happens.
4. Why the build order matters, and when two traversals still aren't enough.

The approach (from preorder + inorder)

One traversal alone can't rebuild a tree, because it doesn't show where one subtree ends and the next begins. Two together can. Preorder lists every root before its subtrees, so the next unused preorder value is always the root of the subtree you're building. Inorder puts every root between its left and right subtrees, so finding the root in inorder splits the remaining values into a left part and a right part.

Rebuilding from preorder 6, 2, 1, 4, 9 and inorder 1, 2, 4, 6, 9:

Map<Integer, Integer> inorderIndex; // value -> index, built once up front
int preIdx = 0;

TreeNode build(int[] preorder, int inStart, int inEnd) {
    if (inStart > inEnd) return null;
    int rootVal = preorder[preIdx++];               // next unused preorder value IS the current root
    TreeNode root = new TreeNode(rootVal);
    int mid = inorderIndex.get(rootVal);              // where the root splits inorder into left/right
    root.left  = build(preorder, inStart, mid - 1);   // must build left before right - preIdx is shared, sequential state
    root.right = build(preorder, mid + 1, inEnd);
    return root;
}

def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    inorder_index = {v: i for i, v in enumerate(inorder)}   # value -> index, built once up front
    pre = iter(preorder)                                    # one shared cursor into preorder

    def build(in_start: int, in_end: int) -> TreeNode | None:
        if in_start > in_end:
            return None
        root = TreeNode(next(pre))              # next unused preorder value IS the current root
        mid = inorder_index[root.val]           # where the root splits inorder into left/right
        root.left = build(in_start, mid - 1)    # must build left before right - the cursor is shared
        root.right = build(mid + 1, in_end)
        return root

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

Two details matter. The map from value to inorder index makes each split an O(1) lookup, which keeps the whole build O(n). And the left subtree must be built before the right one. The preorder cursor is shared, and preorder lists the whole left subtree before the right one.

A second flavor: from inorder + postorder

Postorder lists each root last, after its left and right subtrees. So read postorder from the end, backwards. The tree above has postorder 1, 4, 2, 9, 6, and reading it backwards gives 6, 9, 2, 4, 1. Reading backwards, the right subtree's values come before the left's, so build the right subtree first:

int postIdx = postorder.length - 1;   // starts at the END, walks backward

TreeNode build(int[] postorder, int inStart, int inEnd) {
    if (inStart > inEnd) return null;
    int rootVal = postorder[postIdx--];               // next unused value from the BACK is the current root
    TreeNode root = new TreeNode(rootVal);
    int mid = inorderIndex.get(rootVal);
    root.right = build(postorder, mid + 1, inEnd);     // build RIGHT before LEFT - the cursor is walking backward
    root.left  = build(postorder, inStart, mid - 1);
    return root;
}

def build_tree(inorder: list[int], postorder: list[int]) -> TreeNode | None:
    inorder_index = {v: i for i, v in enumerate(inorder)}
    post = reversed(postorder)                  # the cursor starts at the END and walks backward

    def build(in_start: int, in_end: int) -> TreeNode | None:
        if in_start > in_end:
            return None
        root = TreeNode(next(post))             # next unused value from the BACK is the current root
        mid = inorder_index[root.val]
        root.right = build(mid + 1, in_end)     # build RIGHT before LEFT - the cursor is walking backward
        root.left = build(in_start, mid - 1)
        return root

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

It's the preorder version mirrored: the cursor runs the other way, so the build order flips too.

Where you'll see it

In real systems you'd usually save a tree with null markers (see Serialize and Deserialize), which needs only one traversal. Rebuilding from two traversals is mainly an interview classic. It's a good test of understanding what each traversal order actually tells you.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Building from preorder and inorder, a solution builds the right subtree first. What goes wrong?

2. With inorder and postorder, why start at the end of postorder, and why build the right subtree first?

3. Why does the value-to-index map change the complexity, not just the speed?

Key takeaways

• Preorder or postorder gives each subtree's root. Inorder splits that subtree into left and right.
• With preorder, read forwards and build left before right.
• With postorder, read backwards and build right before left.
• A value-to-index map keeps the build O(n).
• Both bugs are the same mistake: building the subtrees in an order that doesn't match the cursor's direction.