BST Construct From Preorder

Description

A BST can be rebuilt from its preorder list alone. You don't need a second traversal or any null markers, because the BST order already tells you where each subtree ends. This skill teaches the O(n) rebuild: one cursor that only moves forward, and a bound that says how large a value can be and still belong to the current subtree. It also covers the mirror-image rebuild from postorder.

A general binary tree can't be rebuilt from its preorder traversal alone: preorder tells you each subtree's root but not where its left subtree ends and its right subtree begins - you need inorder as well (see Binary Tree Reconstruction). A BST is different. Its inorder is just its values in sorted order, so the "where does the left subtree end" question already has an answer: at the first value too large to belong there.

We'll go from simple to more technical:

1. The pattern: a shared cursor and an upper bound.
2. A second flavor: rebuilding from postorder (read backward, lower bound, right first).
3. Where this pays off: storing an ordered structure as one list.
4. What breaks it, and why repeated insertion is the slow way.

The approach

int idx = 0;

TreeNode bstFromPreorder(int[] preorder) {
    return build(preorder, Integer.MAX_VALUE);
}

TreeNode build(int[] preorder, int bound) {
    if (idx == preorder.length || preorder[idx] > bound) return null;   // out of values, or it belongs further up
    TreeNode root = new TreeNode(preorder[idx++]);
    root.left = build(preorder, root.val);     // left subtree: everything below root's own value
    root.right = build(preorder, bound);       // right subtree: everything still below the inherited bound
    return root;
}

def bst_from_preorder(preorder: list[int]) -> TreeNode | None:
    idx = 0

    def build(bound: float) -> TreeNode | None:
        nonlocal idx
        if idx == len(preorder) or preorder[idx] > bound:
            return None                      # out of values, or it belongs further up
        root = TreeNode(preorder[idx])
        idx += 1
        root.left = build(root.val)          # left subtree: everything below root's own value
        root.right = build(bound)            # right subtree: everything still below the inherited bound
        return root

    return build(float("inf"))

The shared idx cursor only moves forward, reading values in the order preorder lists them - a node, then its whole left subtree, then its whole right subtree. The bound says how large a value may be and still belong to the current subtree. The left child gets the node's own value as its bound; the right child inherits the parent's bound. The first value that exceeds a bound ends that subtree and is handed back up to the first ancestor whose bound it fits.

Only an upper bound is ever needed. A value reaches a node's right subtree only after failing the left subtree's bound - so it's already known to be larger than the node, and the lower bound comes for free from the reading order.

A second flavor: rebuilding from postorder

Postorder lists the left subtree, then the right, then the node - the root comes last. So everything mirrors: read the cursor from the end, use a lower bound, and build the right subtree before the left:

int idx;   // starts at postorder.length - 1

TreeNode build(int[] post, int lowerBound) {
    if (idx < 0 || post[idx] < lowerBound) return null;
    TreeNode root = new TreeNode(post[idx--]);
    root.right = build(post, root.val);        // walking backward, the right subtree comes next
    root.left = build(post, lowerBound);
    return root;
}

def bst_from_postorder(post: list[int]) -> TreeNode | None:
    idx = len(post) - 1

    def build(lower_bound: float) -> TreeNode | None:
        nonlocal idx
        if idx < 0 or post[idx] < lower_bound:
            return None
        root = TreeNode(post[idx])
        idx -= 1
        root.right = build(root.val)         # walking backward, the right subtree comes next
        root.left = build(lower_bound)
        return root

    return build(float("-inf"))

Reading backward, postorder becomes "node, right subtree, left subtree" - preorder with the sides swapped. That's why the right child gets the node's value as its (lower) bound and is built first. Building left first, copied from the preorder version, consumes values that belong to the right subtree.

Where you'll see it

Serializing an ordered structure as a single traversal - and rebuilding it in linear time - is a direct payoff of keeping it ordered: a BST (or a sorted index) can be persisted as one preorder list with no null markers and no second traversal, where a general tree needs either null markers or two traversals.

Which tool for which job?

Common mistakes

Check yourself

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

1. Rebuilding from preorder 8 5 1 7 10 12: when the left subtree of 5 is being built (bound 5), which values does it take, and what stops it?

2. Why does the preorder rebuild need only an upper bound, never a lower one?

3. What changes when rebuilding from postorder instead of preorder?

Key takeaways

• A BST can be rebuilt from one traversal because its inorder is simply its sorted values - no second traversal needed.
• One shared cursor plus a bound decides where every value goes: the left child is bounded by the node's value, the right child inherits the parent's bound.
• Preorder needs only an upper bound - the reading order enforces the lower one.
• From postorder, everything mirrors: read backward, use a lower bound, build right before left.
• The bound-cursor rebuild is O(n); repeated insertion is O(n * h), up to O(n^2).