589. Construct Binary Search Tree from Preorder Traversal
A preorder traversal visits the root first, then the whole left subtree, then the whole right subtree. In a binary search tree (BST), every value in a node's left subtree is smaller than the node and every value in its right subtree is larger. Put those two facts together and a preorder listing of distinct values pins down exactly one BST.
Your function receives the integer array preorder — a valid preorder traversal of some BST with all-distinct values — and must rebuild that tree, returning its root node. Create nodes with TreeNode(value) and hang subtrees on their left and right fields.
The judge serializes the tree you return in level order (breadth-first), printing null for a missing child and dropping trailing null tokens, so the one correct tree produces exactly the expected output.
Example 1:
Input: preorder = [8, 5, 1, 7, 10, 12]
Output: [8, 5, 10, 1, 7, null, 12]
Explanation: 8 is the root. The values 5, 1, 7 are all smaller than 8, so they form the left subtree (5 with children 1 and 7); 10 and 12 are larger, so they form the right subtree (10 with right child 12).
Example 2:
Input: preorder = [1, 3]
Output: [1, null, 3]
Explanation: 1 is the root and 3 is larger, so 3 becomes its right child; the left child slot is empty.
Constraints:
- 1 ≤ preorder.length ≤ 100
- 1 ≤ preorder[i] ≤ 10⁸
- All values in preorder are distinct
- preorder is a valid preorder traversal of some binary search tree
Hints:
preorder[0] is always the root. Every later value smaller than it belongs to the left subtree, every larger value to the right subtree — and those two groups are contiguous in the array.
Instead of scanning for the split point, pass down an upper bound: consume values from a shared index as long as they stay below the bound. A node's left subtree is bounded by the node's own value; its right subtree inherits the parent's bound. Each value is consumed once — O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: preorder = [8, 5, 1, 7, 10, 12]
Expected output: [8, 5, 10, 1, 7, null, 12]