Construct BST from Preorder Traversal
Build the BST matching the given preorder sequence (LeetCode 1008).
Open on LeetCode ↗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.
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
python
▶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
Edge cases
Decreasing sequence
Pure left chain; every key admitted under successive tighter bounds.
Single key
Root only.
06
Complexity
Time
O(n)
Space
O(h)
One pointer, bounds pruning.