LeetCode #1008 Medium

Construct BST from Preorder Traversal

Build the BST matching the given preorder sequence (LeetCode 1008).

bstrecursionstack

02

Intuition

Same bounds trick as the GFG version: recurse with an upper bound only — a preorder value less than the bound extends the left side; once a value exceeds it, it belongs to an ancestor's right. One shared index, linear time.

How to spot this pattern

Pre-order gives you the root first, and the BST property tells you where each subsequent value belongs — so one left-to-right pass with an upper bound rebuilds the tree. The bound is the whole idea: a value larger than the current limit cannot belong in this subtree, so the recursion returns and lets an ancestor claim it.

03

Approach

1

Upper bound suffices

build(bound): while the next key < bound, it's in this subtree. Left recursion bounds by the node's value, right by the inherited bound.

2

Stack alternative

Iterate keys; pop stack nodes smaller than the key (finding the parent), attach right, else attach left — same O(n).

3

Why linear

Every key is examined a constant number of times against bounds.

04

Solution & live demo

▶1class Solution:
▶2    def bstFromPreorder(self, preorder):
▶3        self.i = 0
▶4        def build(bound):
▶5            if self.i == len(preorder) or preorder[self.i] > bound:
▶6                return None
▶7            node = TreeNode(preorder[self.i]); self.i += 1
▶8            node.left = build(node.val)
▶9            node.right = build(bound)
▶10            return node
▶11        return build(float("inf"))

05

Common pitfalls

Searching for the split point each time

✗ Wrong

i = next(k for k, v in enumerate(preorder) if v > root_val)
left = build(preorder[1:i]); right = build(preorder[i:])

✓ Right

def build(bound):
    if self.i == len(preorder) or preorder[self.i] > bound:
        return None

Scanning for the boundary and slicing costs O(n²) time and O(n²) memory in copies. The bound parameter decides membership in O(1), so the whole build is a single linear pass.

Passing the wrong bound to the right child

✗ Wrong

node.left = build(node.val)
node.right = build(node.val)

✓ Right

node.left = build(node.val)
node.right = build(bound)

The right subtree is capped by whatever limited this node, not by this node's value — values there are larger than node.val by definition. Reusing node.val rejects every legitimate right child and produces a left-only chain.

Using a local index instead of a shared cursor

✗ Wrong

def build(i, bound):
    ...
    node.left = build(i + 1, node.val)

✓ Right

self.i = 0
# build() advances self.i as it consumes

The right subtree must start wherever the left subtree stopped, and a local index can't know that without returning it. A shared cursor advances as a side effect, so each call naturally resumes where the previous one finished.

06

Edge cases

Decreasing sequence

Pure left chain; every key admitted under successive tighter bounds.

Single key

Root only.

07

Complexity

Time

O(n)

Space

O(h)

One pointer, bounds pruning.