Construct BST from Preorder Traversal
Construct BST from Preorder Traversal: build the BST matching the given preorder sequence (LeetCode 1008).
- 1 <= preorder.length <= 100
- 1 <= preorder[i] <= 1000
- All the values of preorder are unique.
Intuition
To construct bst from preorder traversal, note that a preorder sequence alone determines a binary search tree uniquely — unlike a plain binary tree, which would also need an inorder sequence. The BST ordering property supplies the missing information. The straightforward approach is to insert each value one at a time using standard BST insertion. That works but costs O(n²) on a sorted input, where the tree degenerates into a chain and every insertion walks its full length. The linear solution uses value bounds instead. Preorder visits the root first, then the entire left subtree, then the entire right subtree. Every value in the left subtree is less than the root, and every value in the right subtree is greater. So as you consume the sequence, each position carries an implicit legal range: - Keep consuming values while the next one is below the current upper bound; the first value that exceeds it belongs to an ancestor's right subtree. A single upper bound is enough — the lower bound is implied by the order values are consumed. Build the node, recurse left with the node's own value as the new bound, then recurse right with the inherited bound. One shared index walks the array forward and never backtracks, so every value is examined a constant number of times. An iterative version with an explicit stack achieves the same thing: pop nodes smaller than the incoming key to find its parent, then attach it on the appropriate side.
To construct bst from preorder traversal, 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.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Understand why preorder alone is enough
For a general binary tree, preorder is ambiguous and a second traversal is required. A BST's ordering property removes the ambiguity — knowing a value is smaller than an ancestor already tells you it belongs on the left, so no inorder sequence is needed.
Recurse with an upper bound
Define build(bound). If the next value is greater than bound, this subtree is finished — return null without consuming anything. Otherwise take the value as the current node. A single bound suffices because values arrive in preorder, which implies the lower limit.
Advance one shared index
Keep a single index into the preorder array, shared across every recursive call, and increment it as each value is consumed. The index must never be reset or passed by value, or subtrees will re-read values that belong to a sibling.
Recurse left with the node's value, right with the inherited bound
The left subtree may contain only values below the current node, so pass node.val as its bound. The right subtree may contain anything below the bound this call received, so pass that through unchanged. This pair of bounds is what routes each value to its correct place.
Consider the iterative stack version
Walk the values keeping a stack of ancestors. Pop while the stack top is smaller than the incoming key — the last popped node is the parent, and the key becomes its right child. If nothing pops, the key is the left child of the current top. Same O(n), no recursion depth to worry about on a skewed input.
Cost of the construction
Each value is consumed once and compared against a constant number of bounds, giving O(n) time. Space is O(h) for the recursion or the stack. Compare with repeated BST insertion, which is O(n²) on already-sorted input — the exact case where this bounds approach stays linear.
Solution & live demo
Common pitfalls
Searching for the split point each time
i = next(k for k, v in enumerate(preorder) if v > root_val) left = build(preorder[1:i]); right = build(preorder[i:])
def build(bound):
if self.i == len(preorder) or preorder[self.i] > bound:
return NoneScanning 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
node.left = build(node.val) node.right = build(node.val)
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
def build(i, bound):
...
node.left = build(i + 1, node.val)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.
Edge cases
Pure left chain; every key admitted under successive tighter bounds.
Root only.