Construct Binary Search Tree from Preorder Traversal
01 · Problem
You are given an array preorder containing the preorder traversal (node, then left subtree, then right subtree) of a binary search tree with distinct values. In this BST every value in a node's left subtree is strictly smaller than the node and every value in its right subtree is strictly larger.
Rebuild the BST and return its root. The input always corresponds to exactly one BST, so the answer is unique. The output is the tree in level-order form, with null for missing children and trailing nulls removed.
Aim for an O(n) solution.
02 · Examples
preorder = [8,5,1,7,10,12]
[8,5,10,1,7,null,12]
8 is the root. 5, 1 and 7 are smaller and form the left subtree; 10 and 12 are larger and form the right subtree.
preorder = [1,3]
[1,null,3]
3 is larger than the root 1, so it becomes the right child.
preorder = [4,2,1,3,6,5,7]
[4,2,6,1,3,5,7]
The values build a perfectly balanced BST of height 2.
03 · Constraints
- 011 <= preorder.length <= 100
- 021 <= preorder[i] <= 1000
- 03All values in preorder are unique.
- 04preorder is a valid preorder traversal of some BST.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.