DSA Sheet - Day 20 BST
🌳 DSA Sheet – Day 20: Binary Search Trees (BST)
This section focuses on Binary Search Tree fundamentals. BST problems are highly optimized using ordering properties, making them very common in interviews.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Kth Largest in BST | Solve | Easy | Amazon, Google | |
| Sorted Array to BST | Solve | Easy | Amazon, Adobe | |
| Kth Smallest in BST | Solve | Medium | Amazon, Uber | |
| LCA in BST | Solve | Medium | Meta, Amazon | |
| Validate BST | Solve | Medium | Amazon, LinkedIn |
🧠 Key Approaches
- Kth Smallest/Largest: Inorder traversal gives sorted order
- Sorted Array → BST: Pick middle element recursively
- LCA in BST: Use BST property (go left/right)
- Validate BST: Maintain valid range (min/max)
⚡ Quick Cheatsheet
Kth Smallest (Inorder Traversal)
void inorder(TreeNode* root){
if(!root) return;
inorder(root->left);
// process node
inorder(root->right);
}
Validate BST (Range Check)
bool isValid(TreeNode* root, long minVal, long maxVal){
if(!root) return true;
if(root->val <= minVal || root->val >= maxVal)
return false;
return isValid(root->left, minVal, root->val) &&
isValid(root->right, root->val, maxVal);
}
LCA in BST
while(root){
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;
}
🔥 Pro Tip
BST problems are easier than normal trees if you use properties correctly:
- Left subtree → smaller
- Right subtree → greater
- Inorder → always sorted