Construct BST from Preorder Traversal: Upper Bound Recursion

You are given an array of integers representing the preorder traversal of a binary search tree. Your task is to reconstruct the original BST and return its root. This is LeetCode 1008: Construct Binary Search Tree from Preorder Traversal.

Example: preorder = [8, 5, 1, 7, 10, 12] produces a BST with root 8, left subtree containing 5, 1, 7, and right subtree containing 10, 12.

Why this problem matters

Constructing a BST from a single traversal is a foundational skill that tests whether you really understand two things at once: how preorder traversal works and how BST ordering constraints shape the tree. Unlike building a generic binary tree (which requires two traversal arrays), a BST can be rebuilt from preorder alone because the BST property tells you exactly where each value belongs.

This problem also introduces the upper bound recursion technique, a pattern that shows up in BST validation, serialization, and other tree construction problems.

The key insight

In a preorder traversal, the first element is always the root. Everything after it that is smaller belongs to the left subtree, and everything larger belongs to the right subtree. You could scan the array to find where the split happens, but that would cost O(n) per level and O(n log n) or O(n^2) overall.

The faster approach is to maintain an index into the preorder array and an upper bound. You walk through the array in order, and for each recursive call, you pass a bound that says "values in this subtree must be less than this bound." When the current value exceeds the bound, you know you have left this subtree, so you return None and let the parent handle it.

Here is the algorithm:

1. Start with index 0 and an upper bound of infinity.
2. If the index is out of bounds or the current value exceeds the upper bound, return None.
3. Create a node with the current value and advance the index.
4. Recurse left with the current node's value as the new upper bound.
5. Recurse right with the parent's upper bound (passed down).
6. Return the node.

The solution

def bst_from_preorder(preorder):
    i = 0

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

    return build(float("inf"))

The bound parameter is the secret to making this O(n). Each call to build either creates a node and advances i, or immediately returns None. Since i only moves forward and there are n values, the total work across all calls is O(n).

When you call build(val) for the left child, you are saying "only accept values less than val." When you call build(bound) for the right child, you are saying "accept values up to the bound that was set by the ancestor above." This is how the BST ordering constraint is enforced at every level of the recursion.

Visual walkthrough

Notice how each value is placed exactly once, in the order it appears in the preorder array. The bound mechanism ensures that values "bounce back" to the correct parent when they do not fit in the current subtree.

Complexity analysis

Time is O(n). Each element in the preorder array is visited exactly once. The index i advances from 0 to n across all recursive calls, and each call does O(1) work.

Space is O(n). The recursion stack can go as deep as the height of the tree. In the worst case (a sorted ascending array producing a right-skewed tree, or sorted descending producing a left-skewed tree), the height is n. For a balanced BST, the stack depth is O(log n). The tree itself also uses O(n) space for the n nodes.

The building blocks

1. Preorder traversal property

Preorder visits root, then left subtree, then right subtree. This means the first element is always the root, and the remaining elements naturally divide into a left group (smaller values) followed by a right group (larger values). You do not need a second traversal array to find the split because the BST property provides that information.

2. Upper bound recursion pattern

The bound parameter acts as a gate. Each recursive call says "I will only consume values that fit within my BST constraint." When a value exceeds the bound, the call returns None, effectively saying "this value does not belong to me." The parent then gets a chance to use that value for its right subtree. This pattern avoids scanning the array for partition points and keeps the algorithm linear.

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

This same bound-passing pattern appears in BST validation (LeetCode 98), where you check that every node's value falls within a valid range defined by its ancestors.

Edge cases

• Single node: preorder = [1]. The root is created, both recursive calls return None immediately, and you get a one-node tree.
• Sorted ascending (e.g., [1, 2, 3, 4]): every value goes to the right, producing a right-skewed tree. Recursion depth is O(n).
• Sorted descending (e.g., [4, 3, 2, 1]): every value goes to the left, producing a left-skewed tree. Recursion depth is O(n).
• Two elements: [5, 3] gives root 5 with left child 3. [5, 8] gives root 5 with right child 8.
• All values equal: the problem guarantees distinct values, so this case does not arise. If it did, the BST property (strictly less on the left) would need clarification.

From understanding to recall

You now understand how the upper bound recursion technique builds a BST from preorder in linear time. The idea is simple once you see it: pass a bound, consume values that fit, and return when they do not. But the details matter. You need to remember that the left child gets the current node's value as its bound, the right child inherits the parent's bound, and the index advances globally across all calls.

These details are easy to mix up under pressure. Did the left child get val or bound? Does the index reset between calls? Spaced repetition helps you internalize these specifics so they become automatic. After a few reps, the pattern clicks and you can write it without hesitation.

The upper bound technique also transfers directly to BST validation (LeetCode 98) and BST serialization problems. Drilling this problem builds a foundation for all of them.

Related posts

• Validate Binary Search Tree - Uses a similar min/max bound technique for BST validation
• Construct Binary Tree from Preorder and Inorder - Building trees from two traversal orders
• Serialize and Deserialize Binary Tree - Another tree reconstruction problem

CodeBricks helps you move from understanding a solution to recalling it under pressure. Instead of re-reading explanations, you practice writing the code from scratch at spaced intervals until the pattern is automatic.