π Why This Pattern?
A Binary Search Tree (BST) isnβt just a binary tree β
it comes with ordering constraints:
- Left subtree < Node < Right subtree.
- Inorder traversal = sorted sequence.
π Many problems become much easier once you recognize βBST property can be leveragedβ.
π Core Idea (Template)
- Use inorder traversal to exploit sorted order.
- Use binary search property to prune unnecessary paths.
- Use range constraints when validating or searching.
β Classic Problems
1. Validate BST (LeetCode 98)
Check if tree satisfies BST property.
class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValid(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
}
}
Pattern: DFS with range constraints.
2. Lowest Common Ancestor in BST (LeetCode 235)
Find LCA efficiently using BST property.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
return root; // Split point
}
}
return null;
}
}
Pattern: BST-guided search (pruning).
3. Kth Smallest Element in BST (LeetCode 230)
Inorder = sorted β kth element.
class Solution {
int count = 0, result = -1;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return result;
}
private void inorder(TreeNode node, int k) {
if (node == null) return;
inorder(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inorder(node.right, k);
}
}
Pattern: Inorder traversal β sorted order.
4. Convert Sorted Array to BST (LeetCode 108)
Classic construction problem.
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int l, int r) {
if (l > r) return null;
int mid = (l + r) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, l, mid - 1);
root.right = build(nums, mid + 1, r);
return root;
}
}
Pattern: Divide & Conquer using BST structure.
5. Inorder Successor in BST (LeetCode 285)
Find the smallest node > target.
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
while (root != null) {
if (p.val < root.val) {
successor = root;
root = root.left;
} else {
root = root.right;
}
}
return successor;
}
}
Pattern: BST search + candidate tracking.
6. Range Sum of BST (LeetCode 938)
Sum of values within [low, high]
.
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val < low) return rangeSumBST(root.right, low, high);
if (root.val > high) return rangeSumBST(root.left, low, high);
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}
}
Pattern: Prune branches outside range.
π Advanced Problems
- Serialize & Deserialize BST (LeetCode 449) β exploit preorder with BST constraints.
- Balance BST (LeetCode 1382) β inorder β sorted array β rebuild.
- Closest Value in BST (LeetCode 270) β search path, keep closest.
- Two Sum in BST (LeetCode 653) β inorder (sorted array) + 2-pointer.
π― Quick Pattern Checklist
- β Inorder = sorted β Kth element, 2-sum, median.
- β BST property β prune search (range queries, LCA).
- β Construction β sorted array/list β balanced BST.
- β Successor/Predecessor β candidate tracking in search.
π₯ Key Takeaway:
BST problems are usually simplified to:
- Traversal (sorted)
- Search (guided by property)
- Range/Order queries (pruning)
Top comments (0)