</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Building a BST from preorder with a cursor and (lo, hi) bounds: consume in-range values, else return null

Why one traversal is enough: a general binary tree needs two traversals, but a BST's preorder already encodes every branching decision. Each value's side relative to each ancestor is settled by comparison, so the (lo, hi) window replays those decisions exactly. The same fact means a BST can be serialised without null markers.

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


Core 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²). State it as the baseline, then improve it.

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 shows 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]

Worked recursion trace building a BST from preorder 8,5,1,7,10,12 and the resulting tree

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. A BST can be written out as bare preorder keys with no null markers and reloaded in one pass.
  • Streaming reconstruction. When keys arrive one at a time, the cursor-and-window method consumes each exactly once, with no buffering or sorting.

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.

Construct BST from Preorder Traversal

Core idea: A preorder traversal of a BST lists the root first, then its
entire left subtree, then its entire right subtree. Because it's a search tree,
the values themselves tell you where each node belongs, so you can rebuild
the tree in one left-to-right pass, carrying a (low, high) bound that decides
when to stop going left and start going right. No sorting required.

Problem, rephrased

A librarian walked the library's shelving tree and called out each book's ID the moment she arrived at it, before descending into either branch, and all you have is the recording. You're given that stream as a single array preorder: the values of a binary search tree as visited in preorder (node, then left subtree, then right subtree), all values distinct.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.