Construct BST from Given Keys (Preorder)
Construct BST from Given Keys (Preorder): build the BST whose preorder traversal is the given key sequence.
- 1 <= number of nodes <= 10⁵
- 1 <= node value <= 10⁹
- All values are distinct
Intuition
To construct bst from given keys preorder, note that a preorder sequence alone determines a binary search tree uniquely — unlike a general binary tree, which needs a second traversal to disambiguate. The BST ordering supplies the missing information. The naive approach inserts each key with a standard BST insertion. That is correct but costs O(n·h), degrading to O(n²) on an already-sorted input where the tree becomes a chain. The linear method uses value bounds instead of searching. Preorder emits the root, then the whole left subtree, then the whole right. So as keys arrive in order, each position has an implicit legal range, and the rule is: - Keep consuming keys while the next one falls below the current upper bound; the first key that exceeds it belongs to an ancestor's right subtree. A single upper bound suffices — the lower bound is implied by the order keys are consumed, since preorder never revisits a smaller region. Build a node from the current key, recurse left with that node's value as the new bound, then recurse right with the bound this call inherited. A shared index moves forward and never backtracks, so each key is compared against a constant number of bounds. An iterative version does the same work with an explicit stack: pop ancestors smaller than the incoming key to locate its parent, then attach it left or right accordingly.
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.
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 suffices
For a general binary tree, preorder is ambiguous and a second traversal is required. The BST property removes the ambiguity — a key smaller than an ancestor must go left, so its position is forced rather than chosen.
Recurse with an upper bound
Define build(bound). If the next key exceeds bound, this subtree is complete — return null and consume nothing. Otherwise take the key as the current node and continue. A single bound is enough because preorder moves strictly forward.
Share one index across all calls
Keep a single pointer into the key array, advanced as each key is consumed. It must be shared, not copied — a per-call copy would let sibling subtrees re-read the same keys and build a wrong tree.
Pass the right bound to each side
Recurse left with node.val as the bound, since the left subtree may hold only smaller keys. Recurse right with the bound this call received, since the right subtree is limited by the same ancestor. This pair of bounds routes every key correctly.
Consider the iterative stack version
Walk the keys keeping a stack of ancestors. Pop while the top is smaller than the key — the last popped node is its parent and the key becomes that node's right child. If nothing pops, the key is the left child of the current top. Same O(n), no recursion depth risk on a skewed input.
Cost against repeated insertion
Each key is consumed once and compared against a constant number of bounds, giving O(n) time and O(h) space. Repeated BST insertion is O(n²) on sorted input — precisely the case where the bounds method stays linear.
Solution & live demo
Common pitfalls
Sorting to recover the inorder array
inorder = sorted(pre) # then the two-array construction
if not (lo < pre[idx[0]] < hi):
return NoneCorrect 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
def build(i, lo, hi):
node.left = build(i + 1, lo, val)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
if not (lo <= pre[idx[0]] <= hi):
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.
Edge cases
Degenerate right chain — bounds still route each key correctly.
Return None.