Construct Binary Tree From Preorder and Inorder Traversal

Constructing a binary tree from its preorder and inorder traversals is a recursion question disguised as a puzzle. Given two lists of the same values in different orders, you have to recover the exact shape they came from. Once you see what each list contributes, the code is almost forced: one list tells you the root, the other tells you how many nodes sit on each side of it. The interesting parts are the index bookkeeping, the O(n) version interviewers expect as a follow-up, and knowing when two traversals are not enough.

The problem it solves

You get two lists of distinct values: the preorder traversal of a binary tree (node, then left subtree, then right subtree) and its inorder traversal (left subtree, then node, then right subtree). Rebuild the tree.

For preorder [3, 9, 20, 15, 7] and inorder [9, 3, 15, 20, 7], the tree has 3 at the root, 9 as its left child, and 20 as its right child with children 15 and 7.

Neither list alone fixes the shape. Many different trees share a preorder, and many share an inorder. Together they pin down exactly one tree, as long as the values are distinct.

The intuition

Each traversal knows something the other does not:

• Preorder knows the root. It always visits a node before anything below it, so the first value of any subtree's preorder is that subtree's root.
• Inorder knows the split. It visits the whole left subtree, then the node, then the whole right subtree. Find the root's position in the inorder list, and everything before it is the left subtree, everything after it the right.

That split also tells you the size of the left subtree, say k nodes. Preorder lists the root, then the entire left subtree, then the entire right subtree, so the next k preorder values belong to the left side and the rest to the right. Now you have a smaller preorder and inorder for each side, and the same rule applies to each. Recursion does the rest, and the sizes always match because both lists describe the same subtree.

The lesson's version slices both lists at each step, which is clear but copies data. The faster version never slices. It keeps a dictionary from value to inorder position, so finding the split costs O(1), and it walks through preorder with a single pointer, because the recursion consumes preorder values in exactly the order preorder lists them: root, then everything on the left, then everything on the right.

Watch it run

The animation rebuilds the tree from preorder [3, 9, 20, 15, 7] and inorder [9, 3, 15, 20, 7], highlighting the slice of each list the current call is holding. It begins by pointing out that neither list alone fixes a tree; together they do, and the work is all in where to cut. The first call holds five values. Preorder's first is 3, so that is the root, and inorder puts one of them on its left. The next call holds one value, 9, and inorder shows nothing to its left. Then a call with three values: preorder's first is 20, the root of the right side, with one value on its left. The last two calls hold one value each, 15 and then 7. Five calls, five nodes, and every slice was exactly the size the split promised.

The code

The lesson's slicing version, and the linear version with an index map and a preorder iterator:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build(pre, ino):
    if not pre:
        return None
    root = pre[0]                          # preorder hands you the root first
    k = ino.index(root)                    # inorder: k nodes sit on the left
    return Node(root,
                build(pre[1:k + 1], ino[:k]),
                build(pre[k + 1:], ino[k + 1:]))

def build_fast(pre, ino):
    where = {v: i for i, v in enumerate(ino)}
    nxt = iter(pre)
    def go(lo, hi):                        # this subtree is ino[lo:hi]
        if lo == hi:
            return None
        root = next(nxt)                   # preorder order = the order of the calls
        k = where[root]
        left = go(lo, k)                   # the whole left subtree comes first
        right = go(k + 1, hi)
        return Node(root, left, right)
    return go(0, len(ino))

def postorder(n):
    return postorder(n.left) + postorder(n.right) + [n.val] if n else []

tree = build_fast([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(tree.val, tree.left.val, tree.right.val)      # 3 9 20
print(postorder(tree))                              # [9, 15, 7, 20, 3]

Preorder and postorder together are not enough when a node has a single child, because neither list says which side the child is on:

def preorder(n):
    return [n.val] + preorder(n.left) + preorder(n.right) if n else []

left_child, right_child = Node(1, Node(2)), Node(1, None, Node(2))
print(preorder(left_child) == preorder(right_child),
      postorder(left_child) == postorder(right_child))    # True True

Round trips on 2,000 random trees: build a tree, take its two traversals, rebuild with both versions and compare the shapes:

import random

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

def shape(n):
    return (n.val, shape(n.left), shape(n.right)) if n else None

def random_tree(values):
    if not values:
        return None
    k = random.randrange(len(values))
    return Node(values[k], random_tree(values[:k]), random_tree(values[k + 1:]))

random.seed(18)
ok = True
for _ in range(2000):
    values = random.sample(range(100), random.randint(0, 15))
    t = random_tree(values)
    pre, ino = preorder(t), inorder(t)
    ok &= shape(build(pre, ino)) == shape(t)
    ok &= shape(build_fast(pre, ino)) == shape(t)
print(ok)                                           # True

The complexity

• Slicing version: O(n²) in the worst case. Each call scans inorder with index and copies slices, and a skewed tree makes n calls over lists of length n, n - 1 and so on. On balanced trees it is O(n log n).
• Index-map version: O(n) time. Every node is created once, and every lookup is a dictionary hit. O(n) space for the map.
• Recursion depth: equal to the tree's height, so O(n) for a skewed tree. In Python a chain of a few thousand nodes needs an explicit stack or a higher recursion limit.

Where it goes wrong

• Duplicate values. With preorder [1, 1] and inorder [1, 1], the second 1 could be a left child or a right child. The problem only has a unique answer when values are distinct.
• Off-by-one slices. The left preorder slice is pre[1:k + 1]: skip the root, take k values. pre[1:k] drops a node.
• Building the right subtree first in the iterator version. Preorder lists the left subtree before the right, so the calls must go in that order.
• Using preorder with postorder and assuming it is unique. It is only unique for full binary trees, where every node has zero or two children.
• Searching inorder linearly in the fast version. That brings back the O(n²) worst case.

When it shows up in interviews

It is a common medium, with close relatives: the same problem from inorder and postorder, where the root is the last value and you build the right subtree first, and a tree from preorder alone when it is a binary search tree, where the sorted order plays the role of inorder. Interviewers often ask for the slicing solution first, then for its complexity, then for the O(n) version. Knowing why preorder plus postorder is ambiguous is a strong closing answer.

How to say it in an interview

"Preorder gives me the root of the current subtree: it is always the first value. Inorder gives me the split: everything before the root is the left subtree, everything after is the right, and that also tells me the left subtree's size. I recurse on each side. To make it linear I store each value's inorder index in a hash map and walk preorder with one pointer, because the recursion builds root, left, right in exactly preorder order. That is O(n) time and O(n) space, and it needs distinct values."

Traversal orders are covered in tree traversals, and turning a tree into one list that can be rebuilt on its own is in serialize and deserialize a binary tree.