Construct a BST from Preorder

Construct a BST from Preorder hands you the preorder traversal of a binary search tree and asks you to rebuild the tree. The naive approach scans for split points; the clean trick is to recurse with an upper bound and consume the array in a single pass.

The slow way first

In preorder the first value is always the root. Everything after it splits into a left part (values less than the root) followed by a right part (values greater). So you could scan the rest of the array to find where it flips from "less" to "greater," then recurse on each half.

That works, but each recursion rescans a slice to find its split point, which is O(n²) in the worst case (a skewed tree). We can do better by never rescanning.

The idea: recurse with an upper bound

Walk the array with a single shared index i. Each recursive call is told an upper bound — the largest value allowed in the subtree it is building. The call looks at preorder[i]:

• If i is past the end, or preorder[i] is greater than the bound, this value does not belong here — return None without consuming it.
• Otherwise take preorder[i] as the current node, advance i, then build its left child with bound = this node’s value, and its right child with the same bound it was given.

The bound is what makes the unwinding automatic: a value that is too big to fit the current range causes the recursion to return up the call stack until it finds a range loose enough to hold it.

Walk through it

Step through the animation. The index i consumes the array left to right and never moves backward. Each value drops in as a node the moment a recursive call accepts it. Watch the moments where a value like 7 or 10 is rejected by a tight bound — the recursion unwinds to a looser call, and only then does the value land.

Pseudocode

i = 0
function build(bound):
    if i is past the end OR preorder[i] > bound:
        return None                 # value does not belong in this range
    node = new node with preorder[i]
    i = i + 1
    node.left  = build(node value)  # left subtree: strictly smaller
    node.right = build(bound)        # right subtree: same upper limit
    return node
return build(+infinity)              # root may be anything

The Python solution

def bst_from_preorder(preorder):
    i = 0
 
    def build(bound):
        nonlocal i
        if i == len(preorder) or preorder[i] > bound:
            return None
        node = TreeNode(preorder[i])
        i += 1
        node.left = build(node.val)
        node.right = build(bound)
        return node
 
    return build(float('inf'))

• i is a single shared cursor into preorder; nonlocal i lets the inner function advance it.
• The guard on line 6 is the whole trick: if the next value exceeds bound, it belongs to some ancestor’s right subtree, so we return and let the recursion unwind.
• After taking a node we advance i once — every value is consumed exactly one time.
• build(node.val) builds the left child under a tighter bound (everything left of a node is smaller than it).
• build(bound) builds the right child under the same bound the current call was given.
• The first call uses float('inf') so the root can be any value.

Complexity

Every value is read a constant number of times, so the pass is O(n). The extra space is the recursion stack, O(h) where h is the tree height — O(n) in the worst case, O(log n) when balanced.

When this pattern shows up

Practice