Construct BST from Preorder Traversal — LC 1008 Bounds-Based O(n)

Problem Statement#

LeetCode 1008 — Construct Binary Search Tree from Preorder Traversal | Difficulty: Medium

Given an array of integers preorder which represents the preorder traversal of a BST, construct the tree and return its root. It is guaranteed that there is always only one answer.

Constraints:

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• All values are unique

Input:  preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Input:  preorder = [1,3]
Output: [1,null,3]

Why This Problem Matters#

Constructing a BST from preorder traversal is a FAANG interview problem that tests deep understanding of the BST property. The naive O(n^2) approach — for each value, find the split point between left and right subtrees by scanning — works but misses the elegant O(n) solution. Amazon and Google ask this problem to see whether you can exploit BST invariants to place each node in O(1) time using bounds.

The bounds-based approach is also the correct way to validate a BST (LC 98) — both problems use the same min-max bounds reasoning. Understanding one directly transfers to the other.

The Core Insight#

In a preorder traversal, the first element is always the root. Elements smaller than the root form the left subtree; elements larger form the right subtree. But rather than scanning for the split point each time (O(n^2)), we use min-max bounds:

• Maintain bounds [min, max] for the current subtree
• Process preorder left to right with a global index pointer
• At each call, if preorder[idx] is within (min, max), create a node and advance the pointer
• Otherwise, return null (this value belongs to an ancestor's subtree)

Because preorder visits root before children, and BST ensures each value uniquely belongs to exactly one subtree, each value is claimed by exactly one recursive call — O(n) total.

Visual Dry Run#

Input: [8, 5, 1, 7, 10, 12]

Result: [8, 5, 10, 1, 7, null, 12].

Solution (Optimal)#

class Solution:
    def bstFromPreorder(self, preorder: list) -> 'TreeNode':
        self.idx = 0
 
        def build(min_val, max_val):
            # No more elements or current value out of bounds
            if self.idx >= len(preorder):
                return None
            val = preorder[self.idx]
            if not (min_val < val < max_val):
                return None
 
            # This value belongs here — create node and advance pointer
            node = TreeNode(val)
            self.idx += 1
 
            # Left subtree: values must be less than current val
            node.left = build(min_val, val)
            # Right subtree: values must be greater than current val
            node.right = build(val, max_val)
 
            return node
 
        return build(float('-inf'), float('inf'))

var bstFromPreorder = function(preorder) {
    let idx = 0;
 
    function build(minVal, maxVal) {
        if (idx >= preorder.length) return null;
        const val = preorder[idx];
        if (val <= minVal || val >= maxVal) return null;
 
        const node = new TreeNode(val);
        idx++;
 
        node.left = build(minVal, val);
        node.right = build(val, maxVal);
 
        return node;
    }
 
    return build(-Infinity, Infinity);
};

Time: O(n) — each element claimed by exactly one recursive call Space: O(n) — recursion stack O(h) plus the output tree O(n)

Common Mistakes#

• Using <= in the bounds check — BST uses strict inequalities; all values are unique here
• Finding the split point by scanning (O(n^2) approach) instead of using bounds
• Forgetting to advance the index pointer after creating a node — the index must be a shared state (class variable, list, or closure)
• Building right subtree before left — preorder requires left before right

Interview Tips#

• Explain why the bounds approach is O(n) — each element is processed exactly once
• Contrast with the O(n^2) find-split-point approach to show awareness of complexity
• The shared index pointer (self.idx or closure variable) is the key implementation detail — explain it before coding
• Note the connection to LC 98 (Validate BST) — same min-max bounds reasoning

Follow-up Questions#

• How would you reconstruct a BST from inorder traversal? Inorder of a BST is always sorted, so you would build a balanced BST by choosing the middle element as root.
• Can you build the BST iteratively from preorder? Yes — use a stack. Process elements left to right; maintain a stack of candidate parents.
• How does this differ from constructing a binary tree from preorder + inorder (LC 105)? LC 105 handles arbitrary binary trees (not BSTs), requiring the inorder to identify left/right subtree sizes.
• What if there are duplicate values? Standard BSTs disallow duplicates; if allowed, decide whether duplicates go left or right and adjust bounds accordingly.
• How would you reconstruct from postorder? Process the array right to left with reversed bounds logic — root is the last element.

Key Takeaways#

• BST preorder reconstruction uses min-max bounds to place each value in O(1) time
• The bounds (min_val, max_val) define the valid range for the current subtree root
• Process elements strictly left to right with a shared index pointer — no backtracking needed
• Left subtree call narrows upper bound to val; right subtree call narrows lower bound to val
• Time O(n), space O(h) for the call stack — optimal
• The bounds-based approach is the same reasoning used in BST validation (LC 98) — learn one, know both
• Returning null when a value is out of bounds correctly "rejects" it for the current subtree, letting an ancestor claim it