Construct BST from Given Keys (Preorder)
Build the BST whose preorder traversal is the given key sequence.
Open on GeeksforGeeks ↗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.
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
python
▶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
Edge cases
Sorted (increasing) keys
Degenerate right chain — bounds still route each key correctly.
Empty input
Return None.
06
Complexity
Time
O(n)
Space
O(h)
Each key consumed once.