DSA Sheet - Day 22 BST
🌳 DSA Sheet – Day 22: Binary Search Trees (Part 3)
This section covers advanced BST concepts like serialization, merging trees, and identifying BST structures within a binary tree.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Merge Two BSTs | Solve | Hard | Microsoft, Bloomberg | |
| Serialize & Deserialize BST | Solve | Hard | Amazon, Uber | |
| Inorder Predecessor in BST | Solve | Medium | Microsoft, Meta | |
| Largest BST in Binary Tree | Solve | Medium | Meta, Microsoft | |
| Inorder Successor in BST | Solve | Medium | Amazon |
🧠 Key Approaches
- Merge BSTs: Inorder → merge sorted arrays → rebuild BST
- Serialize/Deserialize: Preorder + bounds OR level order
- Predecessor/Successor: Traverse using BST property
- Largest BST: Bottom-up (return min, max, size, isBST)
⚡ Quick Cheatsheet
Inorder Successor
TreeNode* succ = NULL;
while(root){
if(root->val > key){
succ = root;
root = root->left;
} else {
root = root->right;
}
}
Serialize (Preorder)
void serialize(TreeNode* root){
if(!root) return;
// store root->val
serialize(root->left);
serialize(root->right);
}
Largest BST in Binary Tree
// return {isBST, size, min, max}
// combine left and right subtree results
🔥 Pro Tip
Advanced BST problems test:
- Tree DP (Largest BST)
- Tree encoding (Serialize/Deserialize)
- Ordered traversal logic