Binary Search TreesProblem 8 of 22
Construct BST from preorder traversal
Problem Statement
Given preorder traversal of a Binary Search Tree, construct the BST.
Example:
Preorder: [8, 5, 1, 7, 10, 12]
Constructed BST:
8
/ \
5 10
/ \ \
1 7 12
Explanation: First element (8) is root.
Elements smaller than 8 (5,1,7) form left subtree.
Elements larger than 8 (10,12) form right subtree.
Approach 1: Brute Force (Recursive with Linear Search)
Intuition
In preorder, the first element is root. Elements smaller than root belong to left subtree, elements larger belong to right subtree. Find the partition point and recursively build.
Algorithm
- First element is root
- Find first element greater than root (start of right subtree)
- Recursively build left subtree from elements before partition
- Recursively build right subtree from elements after partition
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode buildBST(int[] preorder, int start, int end) {
if (start > end) return null;
TreeNode root = new TreeNode(preorder[start]);
// Find first element greater than root
int partition = end + 1;
for (int i = start + 1; i <= end; i++) {
if (preorder[i] > root.val) {
partition = i;
break;
}
}
root.left = buildBST(preorder, start + 1, partition - 1);
root.right = buildBST(preorder, partition, end);
return root;
}
public TreeNode bstFromPreorderBruteForce(int[] preorder) {
if (preorder.length == 0) return null;
return buildBST(preorder, 0, preorder.length - 1);
}
}Complexity Analysis
- Time Complexity: O(n^2) - Linear search for partition at each level
- Space Complexity: O(n) - Recursion stack
Approach 2: Better (Using Binary Search for Partition)
Intuition
Since preorder of left subtree contains elements smaller than root and preorder of right subtree contains elements larger than root (and left comes before right), we can use binary search to find the partition point.
Algorithm
- First element is root
- Binary search to find first element greater than root
- Recursively build subtrees
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int findPartition(int[] preorder, int start, int end, int rootVal) {
int lo = start, hi = end;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (preorder[mid] > rootVal) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo;
}
private TreeNode buildBSTBinarySearch(int[] preorder, int start, int end) {
if (start > end) return null;
TreeNode root = new TreeNode(preorder[start]);
int partition = findPartition(preorder, start + 1, end, root.val);
root.left = buildBSTBinarySearch(preorder, start + 1, partition - 1);
root.right = buildBSTBinarySearch(preorder, partition, end);
return root;
}
public TreeNode bstFromPreorderBinarySearch(int[] preorder) {
if (preorder.length == 0) return null;
return buildBSTBinarySearch(preorder, 0, preorder.length - 1);
}
}Complexity Analysis
- Time Complexity: O(n log n) - Binary search at each level
- Space Complexity: O(n) - Recursion stack
Approach 3: Optimal (Using Range/Bound)
Intuition
Process elements one by one maintaining valid ranges. Each element can only be placed if it falls within the valid range. Use upper bound to restrict valid values.
Algorithm
- Use an index to track current element
- Pass upper bound to recursive calls
- If current element > upper bound, return null
- Create node and recursively build left (bound = current value) and right (bound = original bound)
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int idx = 0;
public TreeNode bstFromPreorder(int[] preorder) {
idx = 0;
return buildBST(preorder, Integer.MAX_VALUE);
}
private TreeNode buildBST(int[] preorder, int bound) {
if (idx >= preorder.length || preorder[idx] > bound) {
return null;
}
TreeNode root = new TreeNode(preorder[idx++]);
root.left = buildBST(preorder, root.val);
root.right = buildBST(preorder, bound);
return root;
}
}Complexity Analysis
- Time Complexity: O(n) - Each element processed exactly once
- Space Complexity: O(n) - Recursion stack
Approach 4: Using Stack (Iterative)
Intuition
Use stack to maintain the path from root to current node. For each new element, pop until we find a valid parent.
Algorithm
- First element is root, push to stack
- For each remaining element:
- If smaller than stack top, it's left child of top
- If larger, pop until finding valid parent, it's right child of last popped
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode bstFromPreorderIterative(int[] preorder) {
if (preorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
for (int i = 1; i < preorder.length; i++) {
TreeNode node = new TreeNode(preorder[i]);
if (preorder[i] < stack.peek().val) {
// Left child of stack top
stack.peek().left = node;
} else {
// Find the parent for right child
TreeNode parent = null;
while (!stack.isEmpty() && preorder[i] > stack.peek().val) {
parent = stack.pop();
}
parent.right = node;
}
stack.push(node);
}
return root;
}
}Complexity Analysis
- Time Complexity: O(n) - Each element pushed/popped at most once
- Space Complexity: O(n) - Stack space
Key Takeaways
- Preorder property: Root comes first, then left subtree, then right subtree
- BST property: Left subtree values < root < right subtree values
- Bound technique: Elegant O(n) solution using upper bounds
- Stack approach: Iterative alternative with same complexity
- This is LeetCode #1008 - Construct BST from Preorder Traversal
- Similar problems: Construct from postorder, verify preorder sequence
- The bound technique is applicable to many BST construction problems