GeeksforGeeks Easy

Construct BST from Given Keys (Preorder)

Build the BST whose preorder traversal is the given key sequence.

bstrecursion

02

Intuition

In a BST, order alone determines structure: each preorder value slots into the unique valid position. Recurse with (min, max) bounds — a value inside the current bounds belongs here; outside, it belongs to an ancestor's other side. One pass, no searching.

How to spot this pattern

Preorder plus the BST ordering property is enough — no inorder array required. Each recursive call carries a valid (lo, hi) window, and a value outside it belongs to an ancestor's other branch, which is exactly the signal to stop and return.

03

Approach

1

Bounds encode the ancestors

Every left turn tightens the max; every right turn tightens the min. The next key is consumed by the first frame whose bounds admit it.

2

Single pointer, O(n)

The recursion never re-reads a key — compare with bounds, either consume or return None up the stack.

3

Contrast with insert-one-by-one

Repeated BST insertion is O(n·h); the bounds trick is linear.

04

Solution & live demo

▶1def bst_from_preorder(pre):
▶2    idx = [0]
▶3    def build(lo, hi):
▶4        if idx[0] == len(pre) or not (lo < pre[idx[0]] < hi):
▶5            return None
▶6        val = pre[idx[0]]; idx[0] += 1
▶7        node = TreeNode(val)
▶8        node.left = build(lo, val)
▶9        node.right = build(val, hi)
▶10        return node
▶11    return build(float("-inf"), float("inf"))

05

Common pitfalls

Sorting to recover the inorder array

✗ Wrong

inorder = sorted(pre)
# then the two-array construction

✓ Right

if not (lo < pre[idx[0]] < hi):
    return None

Correct but O(n log n) plus an index map, when the BST property already encodes the ordering. The bounds check does the same work in O(n) with no extra structure.

Passing the index by value

✗ Wrong

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

✓ Right

idx = [0]
...
val = pre[idx[0]]; idx[0] += 1

The left subtree consumes an unknown number of preorder entries, so the right subtree's start index isn't computable from i. A shared mutable cursor advances correctly without that arithmetic.

Using inclusive bounds

✗ Wrong

if not (lo <= pre[idx[0]] <= hi):

✓ Right

if not (lo < pre[idx[0]] < hi):

The bounds are the ancestor values themselves, which are already placed in the tree. Inclusive comparison lets a duplicate of an ancestor be re-inserted below it, corrupting the structure.

06

Edge cases

Sorted (increasing) keys

Degenerate right chain — bounds still route each key correctly.

Empty input

Return None.

07

Complexity

Time

O(n)

Space

O(h)

Each key consumed once.