Build a Binary Tree From Two Traversals, in depth: why preorder or postorder plus inorder is unique, O(n) recursive and stack builds, validation, and why preorder plus postorder is not enough

The three traversals, and what each one tells you

A depth-first traversal visits every node once and differs only in when it emits the node relative to its subtrees. Preorder emits root, then left subtree, then right subtree. Inorder emits left, root, right. Postorder emits left, right, root.

Each order carries a different kind of information. Preorder tells you the root of any subtree immediately: it is the first element of that subtree's span. Postorder tells you the same thing from the other end: the root is the last element. Inorder does not identify the root, but once you know the root, it tells you exactly which values are in the left subtree (everything before the root) and which are in the right (everything after). That is the whole trick. One traversal supplies roots; inorder supplies the split.

A single traversal cannot be enough. The preorder sequence 1, 2 fits both a root 1 with left child 2 and a root 1 with right child 2. With n distinct values there are many tree shapes and only one sequence, so information must be lost.

Why preorder plus inorder is unique

The argument is induction on size. An empty sequence pair gives the empty tree. For a non-empty pair, the first preorder value must be the root, since preorder starts there. Because values are distinct, the root appears at exactly one inorder index m. Everything before index m in inorder is the left subtree and everything after is the right subtree, so the left subtree has exactly m nodes.

Preorder lists the root, then all m left-subtree nodes, then the rest. So the left subtree's preorder is the next m values and its inorder is the first m values. The same holds for the right subtree with the remaining values. Each is a smaller instance, which by induction has exactly one solution. The root, its left subtree and its right subtree are all forced, so the tree is unique.

Postorder plus inorder is the mirror image: the root is the last postorder value, and reading postorder backwards gives root, right subtree, left subtree.

Worked example

Take preorder A B D E C F and inorder D B E A F C.

1. Root is A. A is at inorder index 3, so the left subtree is inorder D B E (3 nodes) and the right is F C.
2. Left subtree: preorder is the next three values, B D E. Root B, at index 1 of D B E, so D is its left subtree and E its right.
3. Right subtree: preorder C F, inorder F C. Root C; F is before C in inorder, so F is C's left child and C has no right child.

The result is A with children B and C; B has children D and E; C has a left child F. Its postorder is D E B F C A, which we will use to check the postorder builder.

An O(n) recursive builder

The textbook version slices arrays and calls index() to find the root in inorder. Both are linear, so a skewed tree costs O(n squared). The fix is two small changes: build a dictionary from value to inorder position once, and instead of slicing, pass the bounds of the current inorder span while a single counter walks through preorder. Because the recursion visits the left subtree before the right, exactly as preorder does, the counter always points at the next subtree's root.

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

def build_pre_in(pre, ino):
    """Rebuild from preorder + inorder. Values must be unique."""
    if len(pre) != len(ino):
        raise ValueError("traversals differ in length")
    pos = {}
    for i, v in enumerate(ino):
        if v in pos:
            raise ValueError(f"duplicate value {v!r}")
        pos[v] = i
    nxt = 0
    def build(lo, hi):                 # builds the subtree whose inorder is ino[lo:hi]
        nonlocal nxt
        if lo == hi:
            return None
        v = pre[nxt]; nxt += 1
        m = pos.get(v)
        if m is None or not lo <= m < hi:
            raise ValueError(f"{v!r} cannot be the root of inorder[{lo}:{hi}]")
        node = Node(v)
        node.left = build(lo, m)       # left first: preorder is root, left, right
        node.right = build(m + 1, hi)
        return node
    return build(0, len(ino))

The check lo <= m < hi is not decoration. Without it, a pair of sequences that do not describe the same tree can produce a wrong tree without an error, or read past the end of preorder. With it, any value that is not in the current span is rejected the moment it appears. Together with the length check and duplicate check, this means that if the function returns, the result has exactly the given traversals.

The postorder version consumes postorder from the end and must build the right subtree before the left, because postorder read backwards is root, right, left:

def build_post_in(post, ino):
    """Rebuild from postorder + inorder: consume postorder from the end, right subtree first."""
    pos = {v: i for i, v in enumerate(ino)}
    if len(pos) != len(ino) or len(post) != len(ino):
        raise ValueError("duplicates or length mismatch")
    nxt = len(post) - 1
    def build(lo, hi):
        nonlocal nxt
        if lo == hi:
            return None
        v = post[nxt]; nxt -= 1
        m = pos.get(v)
        if m is None or not lo <= m < hi:
            raise ValueError(f"{v!r} cannot be the root of inorder[{lo}:{hi}]")
        node = Node(v)
        node.right = build(m + 1, hi)  # postorder read backwards is root, right, left
        node.left = build(lo, m)
        return node
    return build(0, len(ino))

A stack-based builder for deep trees

Recursion depth equals tree height. A balanced tree of a million nodes is about 20 levels deep, but a skewed tree, a sorted insert into an unbalanced BST, or a linked-list-shaped parse tree is n levels deep. CPython's default recursion limit is 1000, and raising it only moves the crash to the C stack. In Java or C++ the equivalent failure is a stack overflow.

The iterative build keeps a stack of nodes whose right child is not yet known. Walk through preorder. While the top of the stack equals the next inorder value, that node's left subtree is complete in inorder terms, so pop it and advance the inorder pointer. If anything was popped, the new value is the right child of the last node popped; otherwise it is the left child of the top. Each node is pushed and popped once, so it is O(n) time with O(h) extra space.

def build_pre_in_iter(pre, ino):
    """Stack-based rebuild, no recursion. Assumes consistent input: verify afterwards."""
    if not pre:
        return None
    root = Node(pre[0]); stack = [root]; j = 0
    for v in pre[1:]:
        node, parent = Node(v), None
        while stack and stack[-1].val == ino[j]:   # finished left spines: climb
            parent = stack.pop(); j += 1
        if parent is not None:
            parent.right = node        # climbed: v is the right child of the last node popped
        else:
            stack[-1].left = node      # still descending left
        stack.append(node)
    return root

def verify(root, pre, ino):
    """Recompute both traversals iteratively and compare."""
    got_pre, got_in, stack, node = [], [], [], root
    while stack or node:
        while node:
            got_pre.append(node.val); stack.append(node); node = node.left
        node = stack.pop(); got_in.append(node.val); node = node.right
    return got_pre == pre and got_in == ino

This version is shorter but trusts its input: given inconsistent sequences it can return a wrong tree or fail with an index error. Pair it with verify, which recomputes both traversals without recursion and compares them, at the cost of one more O(n) pass.

Results from running the code

The builders were run on the worked example, on bad inputs, on a 5,000-node left-skewed chain, and fuzzed against 2,000 random trees of 1 to 60 nodes, rebuilding each with all three builders and checking that the traversals match. Timings are from one run on the authoring machine with the recursion limit raised to 20,000 for both recursive builders:

pre+in   : A(B(D,E),C(F,-))
postorder: DEBFCA
post+in  : A(B(D,E),C(F,-))
iterative: A(B(D,E),C(F,-))
rejected: 2 cannot be the root of inorder[0:1]          # pre [1,2,3], in [3,1,2]
rejected: 'C' cannot be the root of inorder[4:6]        # inorder ends ...F, X
rejected: duplicate value 1                             # [1,2,1] twice
recursive: RecursionError at n = 5000 limit 1000        # left-skewed chain
iterative deep ok: True
n=1000: slicing+index 22.9 ms, dict+bounds 1.2 ms
n=2000: slicing+index 72.2 ms, dict+bounds 1.8 ms
n=4000: slicing+index 306.5 ms, dict+bounds 3.8 ms
fuzz ok: 2000 random trees, 3 builders each

The bad-input lines show what the bounds check buys. For preorder 1 2 3 with inorder 3 1 2, the root is 1 and the left span holds only 3, so 2 cannot come next. Not every unusual pair is invalid, though: preorder A B C with inorder A C B is a real tree, A with right child B whose left child is C, and the builder correctly accepts it. The timing lines show the quadratic cost of slicing plus index() on skewed input against the linear builder.

Why preorder plus postorder is ambiguous

Both preorder and postorder identify roots, and neither tells you which side a child is on. For a root 1 with a single child 2, both trees, child on the left or on the right, have preorder 1 2 and postorder 2 1. Only inorder distinguishes them: 2 1 versus 1 2.

The ambiguity arises exactly at nodes with one child. If every node has zero or two children, a full binary tree, the pair is unique: the value after the root in preorder is the left child, its position in postorder tells you where the left subtree ends, and the rest is the right subtree. For a general tree with k single-child nodes, each one can independently go either way, so 2 to the power k trees share both traversals. A builder for this pair must pick a convention, usually putting a lone child on the left, and document it.

The same reasoning explains serialization formats. A preorder sequence with explicit null markers for missing children is unique by itself, because the markers say which side is empty. That is why tree serializers emit nulls instead of relying on two traversals.

Duplicates and other failure modes

• Duplicate values. With repeated values, the root's position in inorder is not unique, and distinct trees can share both traversals: a root 1 with left child 1, and a root 1 with right child 1, both give preorder 1 1 and inorder 1 1. Reject duplicates, or rebuild from (value, unique id) pairs.
• Mismatched inputs accepted silently. Builders without the span check return a tree for inputs that describe none. Validate in the builder or verify afterwards.
• Quadratic time. Slicing and index() look linear on balanced test trees and explode on skewed production data.
• Stack overflow. Recursion fails on deep trees; use the stack version for untrusted or skewed input.
• Unhashable or unequal values. The index map needs hashable values with consistent equality; floating-point NaN never equals itself and breaks the lookup.

Where this is used, and trade-offs

In practice, reconstruction from two traversals appears in tests and tooling more than in storage. It checks a tree implementation: generate random trees, emit two traversals, rebuild, and compare, as the fuzz test above does. It reconstructs expression and syntax trees from logs that recorded traversal orders. And it is the underlying reason two orders are needed when nulls are not stored.

For storage, prefer a single preorder with null markers: one sequence, no uniqueness requirement on values, and a simple streaming decoder. If values are BST keys, preorder alone suffices because the BST order gives you inorder for free. Choose the recursive builder when trees are known to be shallow and you want the validation built in; choose the stack builder plus verification for untrusted or deep input.

To continue, see BST insert, search and delete, BST validation, which uses the same bounds idea, Morris traversal for O(1)-space walks, and the Cartesian tree, another structure defined by an inorder sequence and a root rule.

What to do next

1. Rebuild the A B D E C F example on paper, then run the recursive builder and check the postorder you get is D E B F C A.
2. Replace any slicing-and-index builder in your code with the index map and span bounds.
3. Add the length, duplicate and span checks, and write tests for each rejection message.
4. Run your builder on a 5,000-node skewed chain; if it overflows, switch to the stack version plus verify.
5. Write a fuzz test: random trees, two traversals, rebuild, compare, for a few thousand cases.
6. If you are designing a format, store preorder with null markers instead of two traversals.