DSA Sheet - Day 19 Binary Trees
🌳 DSA Sheet – Day 19: Binary Trees (Advanced)
This section covers advanced binary tree problems frequently asked in top interviews. These problems test recursion depth, tree traversal mastery, and edge-case handling.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Flatten Binary Tree to Linked List | Solve | Medium | Amazon, Microsoft | |
| Maximum Path Sum | Solve | Hard | Google, Amazon | |
| Maximum Width of Binary Tree | Solve | Medium | Uber, Microsoft | |
| Construct Tree from Inorder & Postorder | Solve | Medium | Amazon, Microsoft | |
| Zigzag Level Order Traversal | Solve | Medium | Meta, Amazon | |
| Kth Ancestor of a Node | Solve | Medium | Amazon |
🧠 Key Approaches
- Flatten Tree: Preorder traversal → modify pointers
- Max Path Sum: Track max gain + global answer
- Max Width: BFS + index mapping
- Build Tree: Postorder root + inorder partition
- Zigzag: BFS + alternate direction
- Kth Ancestor: Backtracking from node to root
⚡ Quick Cheatsheet
Maximum Path Sum
int maxi = INT_MIN;
int solve(TreeNode* root){
if(!root) return 0;
int l = max(0, solve(root->left));
int r = max(0, solve(root->right));
maxi = max(maxi, l + r + root->val);
return root->val + max(l, r);
}
Flatten Binary Tree
// reverse preorder: right → left
// maintain previous pointer
Zigzag Traversal
bool leftToRight = true;
// reverse direction at each level
🔥 Pro Tip
Binary Tree advanced patterns:
- Use recursion to return useful information (height, sum, etc.)
- Maintain global variables when needed
- Always think: "What should my function return?"