DSA problem
Construct Binary Search Tree from Preorder Traversal
Given an array preorder of integers representing the preorder traversal of a BST (root, then left subtree, then right subtree), construct the original BST and return its root. The input is guaranteed to be a valid preorder of some BST with distinct values.
A direct simulation builds the tree by inserting each value one at a time using BST insert, costing O(n^2) in the worst case (a sorted input creates a skewed tree). We can do strictly better by exploiting how a preorder traversal interacts with the BST ordering invariant.
In a preorder of a BST, the first value is the root. Then comes the entire left subtree (whose values are all less than the root) followed by the entire right subtree (whose values are all greater). This means we can partition the rest of the array around the root in linear time — but a clean way to avoid the explicit partition is to thread the array with a shared index and an upper bound.
The optimal solution uses a recursive helper that takes a bound argument and a shared index i (a single-element wrapper). At each call: if i >= n or preorder[i] > bound, return null. Otherwise create a node with value preorder[i], advance i, then recursively build the left subtree with bound = current value (left subtree values must be strictly less than the current node) and the right subtree with the inherited bound. This visits each value exactly once, giving O(n) time. Space is O(h) for the recursion stack.
Examples
preorder = [8,5,1,7,10,12][8,5,10,1,7,null,12]preorder = [1,3][1,null,3]preorder = [3,1,2][3,1,null,null,2]Constraints
- 1 <= preorder.length <= 100
- 1 <= preorder[i] <= 10^8
- All values of preorder are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.