Rebuilding a tree from traversals

One traversal list does not tell you the tree: many trees give the same pre-order. But two lists together can. This lesson rebuilds a tree from its pre-order and in-order lists, proves the answer is the only one, and shows which pairs of lists are enough.

Two lists fix the tree

Suppose all values are different, and you have the tree’s pre-order and in-order lists. Two facts from lesson 2 do all the work:

1. Pre-order starts with the root. After the root come all the values of the left subtree, then all the values of the right subtree.
2. In-order has the root in the middle. Every value before the root is in the left subtree, and every value after it is in the right subtree.

So: read the root from the front of pre-order. Find it in in-order. The number of values to its left, say L, is the size of the left subtree. Then the next L pre-order values are the left subtree’s pre-order, and the rest are the right subtree’s. Now you have the same problem twice, on two smaller pairs of lists.

Why only one? By induction on the number of nodes (proving it for small trees first, then for bigger ones using the smaller cases). An empty list gives only the empty tree. For a bigger tree, the root is forced: it is the first pre-order value. Its left and right subtrees have forced lists, as shown above, and each is smaller, so each is a single tree by induction. So the whole tree is forced.

Step by step

The figure rebuilds the tree from lessons 1 and 2. The nxt pointer moves along pre-order, one root at a time. The window shows which part of in-order the current subtree covers.

Notice two things. First, the pre-order list is used strictly from left to right, never jumping. That is because the recursion builds each left subtree completely before the right one, which is exactly the order pre-order lists them. Second, the in-order list is never changed or copied. Each subtree is just a range lo..hi of it.

The code and its cost

def build_tree(preorder, inorder):
    where = {v: i for i, v in enumerate(inorder)}   # value -> in-order place
    nxt = 0

    def make(lo, hi):                    # build the subtree for inorder[lo..hi]
        nonlocal nxt
        if lo > hi:
            return None                  # an empty range is an empty tree
        v = preorder[nxt]
        nxt += 1
        node = TreeNode(v)
        node.left = make(lo, where[v] - 1)
        node.right = make(where[v] + 1, hi)
        return node

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

nonlocal nxt lets the inner function change the outer variable nxt, so all the calls share one position in pre-order.

Each call makes one node, plus empty calls at the missing children, so there are about 2n calls, each O(1). With the dict the rebuild takes O(n) time. A common shortcut, slicing the lists and calling inorder.index(v) in each call, costs O(n) per call on a path-shaped tree, so O(n²) in all. The recursion is h + 1 calls deep, as usual.

Which pairs work

• Post-order and in-order also work. Post-order ends with the root, so take roots from the back, and build each right subtree before the left one.
• Level order and in-order also work: the first value of level order is the root.
• Pre-order and post-order do not, in general. The tree “1 with left child 2” and the tree “1 with right child 2” both have pre-order [1, 2] and post-order [2, 1]. Without in-order, nothing says which side a lone child is on. (If every node has 0 or 2 children, the pair does work.)
• Repeated values break all of this: in the list [1, 1], which 1 is the root of in-order? The rule needs different values.