#1008
Construct Binary Search Tree from Preorder Traversal
Medium Upper-bound recursion
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rebuild a BST from its preorder traversal.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rebuild a BST from preorder.
Why this works: give each node an upper limit; a value goes into the current subtree only while it's below that limit.
Example: [8, 5, 1, 7, 10, 12]
8 → left (below 8): 5 → 1, 7right: 10 → 12
✦Hints open one at a time
The first value is the root; following smaller values form the left subtree.
Pass an upper bound: a node may be placed only if its value is below the bound.
↗Approach
Keep an index into preorder. build(bound): if the next value is above the bound (or none left), return null. Otherwise create the node, build left with bound = node.val, build right with the same outer bound.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
private int i = 0;
public TreeNode bstFromPreorder(int[] preorder) {
return build(preorder, Integer.MAX_VALUE);
}
private TreeNode build(int[] pre, int bound) {
if (i == pre.length || pre[i] > bound) return null;
TreeNode root = new TreeNode(pre[i++]);
root.left = build(pre, root.val); // left values must be smaller than root
root.right = build(pre, bound);
return root;
}
}!Common mistake
Inserting values one by one — O(n²) for skewed input.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon