Construct a BST from a preorder traversal
MediumBuild with an upper bound
Problem
Build a BST from its preorder traversal and return the root.
Insert the preorder values one by one, each sliding into its correct BST position.
The idea
Preorder gives the root first, then its left subtree, then its right. Walking the array once while carrying an upper bound tells you when the left subtree has ended and the right begins, so the tree is rebuilt in O(n) rather than O(n²).
The trick
- Recurse with a bound; return as soon as the next value exceeds it.
- Sorting the preorder gives the inorder, which is the slower O(n log n) route.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [8,5,1,7,10,12] Values: 8, 5, 1, 7, 10, 12.
1i=02build(bound):3 if i==n or pre[i]>bound: return null4 node=Node(pre[i++])5 node.left=build(node.val)6 node.right=build(bound)7 return nodeInput
- array
- [8, 5, 1, 7, 10, 12]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- preorder = [8,5,1,7,10,12]
- Output:
- [[8], [5, 10], [1, 7, 12]]
- Explanation:
- Insert in order to rebuild the BST.
Example 2
- Input:
- preorder = [1,3]
- Output:
- [[1], [3]]
- Explanation:
- 3 goes to the right of 1.
Example 3
- Input:
- preorder = [5]
- Output:
- [[5]]
- Explanation:
- Single node.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.