DSA Sheet - Day 18 Binary Trees
🌳 DSA Sheet – Day 18: Binary Trees (Part 3)
This section covers advanced binary tree concepts like tree views, Lowest Common Ancestor (LCA), and tree construction from traversals — highly important for interviews.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Bottom View of Binary Tree | Solve | Medium | Amazon, Google | |
| Top View of Binary Tree | Solve | Medium | JP Morgan, Flipkart | |
| Lowest Common Ancestor (LCA) | Solve | Medium | Google, Adobe | |
| Kth Level of Tree | Solve | Medium | Amazon | |
| Construct Tree from Inorder & Preorder | Solve | Medium | Apple, Uber | |
| Transform to Sum Tree | Solve | Medium | VMWare |
🧠 Key Approaches
- Top/Bottom View: Level order + horizontal distance (map)
- LCA: Recursive divide & conquer
- Kth Level: BFS traversal
- Build Tree: Preorder index + inorder mapping
- Sum Tree: Postorder traversal (bottom-up)
⚡ Quick Cheatsheet
Lowest Common Ancestor (LCA)
TreeNode* LCA(TreeNode* root, TreeNode* p, TreeNode* q){
if(!root || root == p || root == q)
return root;
auto left = LCA(root->left, p, q);
auto right = LCA(root->right, p, q);
if(left && right) return root;
return left ? left : right;
}
Build Tree (Preorder + Inorder)
TreeNode* build(int l, int r){
if(l > r) return NULL;
int val = preorder[idx++];
TreeNode* root = new TreeNode(val);
int mid = mp[val];
root->left = build(l, mid - 1);
root->right = build(mid + 1, r);
return root;
}
Top View / Bottom View
map mp;
queue> q;
// {node, horizontal distance}
🔥 Pro Tip
These are high-frequency interview patterns:
- LCA → asked everywhere
- Tree construction → tests deep understanding
- Tree views → BFS + mapping pattern