Build from Preorder

What is this?

Hand someone the numbers 8, 5, 1, 7, 10, 12 and tell them it is a binary search tree written down root-first. They can rebuild it exactly — no ambiguity, no second traversal, no null markers. The ordering invariant supplies everything the missing information would have.

The elegant implementation never searches for where the left subtree ends. It walks the list once, carrying a window of legal values, and a value outside that window simply refuses to be consumed — reappearing later, in the branch where it is legal.

💡 Fun fact: the reason this works with one traversal, when a general binary tree needs two, is that a BST's preorder is not merely a list of values — it is a list that already encodes every branching decision. Every value's side relative to each ancestor is determined by comparison, so the (lo, hi) window replays those decisions exactly. The same insight means a BST can be serialised without any null markers at all, typically halving the payload.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: carry a (lo, hi) window down the recursion and consume values with a shared cursor. A value outside the window belongs to an ancestor's other branch — so you leave it alone, return null, and let the call that can accept it pick it up.

1. The bounds walk

def bst_from_preorder(preorder):
    i = 0

    def build(lo, hi):
        nonlocal i
        if i == len(preorder):
            return None
        val = preorder[i]
        if val < lo or val > hi:        # belongs to an ancestor's other branch
            return None                 # note: NOT consumed
        i += 1
        node = TreeNode(val)
        node.left  = build(lo, val)     # left subtree: strictly less
        node.right = build(val, hi)     # right subtree: strictly greater
        return node

    return build(float('-inf'), float('inf'))

The crucial line is the early return that does not advance the cursor. The value is peeked, judged out of range, and left in place — so the recursion unwinds until it reaches a call whose window accepts it. That single discipline is what turns an O(n²) "find the split point" algorithm into a linear one.

2. The alternative, and why it is worse

The obvious approach: the first value is the root, then scan forward for the first value greater than it — that is where the right subtree begins — and recurse on the two halves. It is correct and easy to explain, but each level rescans, so a skewed tree costs O(n²). Worth stating as the baseline, then improving.

A third option is to sort the values to obtain the inorder traversal and apply the standard preorder-plus-inorder reconstruction. It works, costs O(n log n), and quietly reveals that you did not notice the invariant already gave you the ordering.

3. A 30-second worked example

preorder = [8, 5, 1, 7, 10, 12]

build(-inf, +inf)  peek 8   in range  → consume, node 8
  build(-inf, 8)   peek 5   in range  → consume, node 5
    build(-inf, 5) peek 1   in range  → consume, node 1
      build(-inf,1) peek 7  7 > 1     → null (7 not consumed)
      build(1, 5)   peek 7  7 > 5     → null (7 not consumed)
    → node 1 complete
    build(5, 8)    peek 7   in range  → consume, node 7
      build(5,7)   peek 10  10 > 7    → null
      build(7,8)   peek 10  10 > 8    → null
    → node 7 complete
  → node 5 complete, with children 1 and 7
  build(8, +inf)   peek 10  in range  → consume, node 10
    build(8,10)    peek 12  12 > 10   → null
    build(10,+inf) peek 12  in range  → consume, node 12
  → node 10 complete
                                  8
                                 / \
                                5   10
                               / \    \
                              1   7    12

Watch the 7: it is peeked and rejected twice before the call with window (5, 8) finally accepts it. Nothing was scanned or searched — the rejections are the search.

4. Where you'll actually meet this

• Compact serialisation. Sending a BST as bare values, with no structural markers, is a real bandwidth saving in caches and RPC payloads.
• Database index restore. Rebuilding an index from a sorted or root-first dump uses the same bounds reasoning.
• Config and schema hydration. Reconstructing a hierarchy from a flat ordered list, where the ordering implies nesting.
• Undo and snapshot systems. Restoring a tree-shaped state from a linear log.
• Parsers. Bounds-driven descent is how precedence-climbing parsers decide when a subexpression has ended — the same "this token is not mine" signal.

5. Problems in this chapter

▶ Construct Binary Search Tree from Preorder Traversal

Rebuild the BST from its preorder values. One cursor, one (lo, hi) window, one pass.
Pattern: bounds-driven descent with a shared cursor. Target: O(n) time, O(h) space.

6. Common pitfalls 🚫

• Consuming the value before the range check. The cursor must only advance for values this call accepts; otherwise values vanish into the wrong branch.
• Making the cursor a parameter. It must be shared across the whole recursion — nonlocal, an instance field, or a one-element list. Passing it by value silently duplicates state.
• Using <= on both sides. The BST here has distinct values; strict comparisons on both bounds keep the windows disjoint.
• Scanning for the split. Correct, but O(n²) on a skewed tree, which is exactly the input an interviewer will choose.
• Sorting to recover inorder. O(n log n) and it discards the invariant you were given.
• Forgetting the exhausted-cursor check. Once every value is consumed, further calls must return null rather than index past the end.

7. Key takeaways

1. A BST's preorder is unambiguous. The ordering invariant replaces the second traversal a general tree would need.
2. Carry a window, not a split point. (lo, hi) replays every branching decision without any searching.
3. Rejection is the mechanism. A value outside the window is left in place and picked up by the call that can accept it.
4. One shared cursor across the whole recursion — never a copied parameter.
5. No null markers required, which is why BST serialisation is so much more compact than general-tree serialisation.
6. Why interviewers like it: three solutions exist at O(n log n), O(n²) and O(n), and which one you reach for shows exactly how well you understand what a BST guarantees.

Order: Construct BST from Preorder Traversal.

The general-tree version of this — rebuilding from a pair of traversals, where the split has to be located rather than deduced — is in Binary Tree / Construct and Convert.