Tags
- ⭐ = solved in first try
- 📍 = revisit
- 🔥 = important
- ⚠️ = solved but edge case missed
- 👀 = solved but had to see little solution first
- 🐢 = solved, but less optimized
- 💀 = out of the box
- no tag = pending/not started
7. Pattern: Trees
7.1 Traversals (DFS — Recursive & Iterative)
💡 Signal: “inorder”, “preorder”, “postorder”, “traverse the tree”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Inorder Traversal (easy) | Left → Root → Right. Iterative: push all lefts, pop, go right | ||
| 2. Preorder Traversal (easy) | Root → Left → Right. Iterative: push right first, then left | ||
| 3. Postorder Traversal (easy) | Left → Right → Root. Trick: modified preorder + reverse | ||
| 4. N-ary Tree Preorder Traversal (easy) | Same logic, just loop through all children | ||
| 5. N-ary Tree Postorder Traversal (easy) | Process children first, then root |
7.2 Traversals (BFS — Level Order)
💡 Signal: “level order”, “level by level”, “breadth first”, “zigzag”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Level Order Traversal (medium) | Queue + process size nodes per level | ||
| 2. Level Order Traversal II (medium) | Same as above, reverse result at end | ||
| 3. Zigzag Level Order (medium) | Reverse alternate levels | ||
| 4. Average of Levels (easy) | Level-by-level BFS, compute avg per level | ||
| 5. Largest Value in Each Row (medium) | Track max per level during BFS | ||
| 6. Maximum Level Sum (medium) | Sum each level, track max sum and its level number | ||
| 7. Maximum Width (medium) | Assign index: left=2i, right=2i+1. Width = last−first+1 | ||
| 8. Add One Row to Tree (medium) | BFS to depth−1, insert new nodes | ||
| 9. N-ary Tree Level Order (medium) | Same BFS pattern, loop children instead of left/right | ||
| 10. Even Odd Tree (medium) | Even levels: odd values strictly increasing. Odd levels: reverse |
7.3 Tree Properties (Depth, Balance, Symmetry)
💡 Signal: “depth”, “height”, “balanced”, “symmetric”, “same tree”, “subtree”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Maximum Depth (easy) | 1 + max(left, right). Base: null → 0 | ||
| 2. Minimum Depth (easy) | ⚠️ If one child null, go to other child (not 0) | ||
| 3. Balanced Binary Tree (easy) | O(N): return −1 for unbalanced subtree as sentinel | ||
| 4. Same Tree (easy) | Both null → true. One null → false. Compare vals + recurse | ||
| 5. Symmetric Tree (easy) | Like Same Tree but compare left↔right mirror | ||
| 6. Invert Binary Tree (easy) | Swap left and right children at every node recursively | ||
| 7. Diameter of Binary Tree (easy) | At each node: leftHeight + rightHeight. Track global max | ||
| 8. Binary Tree Tilt (easy) | Tilt = | leftSum − rightSum | |
| 9. Merge Two Binary Trees (easy) | If one null, return other. Else sum vals + merge children | ||
| 10. Subtree of Another Tree (easy) | At each node check isSameTree. If not, try left and right | ||
| 11. Univalued Binary Tree (easy) | All nodes same value. DFS check val == root.val | ||
| 12. Max Depth N-ary Tree (easy) | Same pattern, max over all children |
7.4 Side Views (Left, Right, Top, Bottom, Boundary)
💡 Signal: “right side view”, “left view”, “top view”, “bottom view”, “boundary”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Right Side View (medium) | BFS: last node of each level. DFS: right child first, level==size | ||
| 2. Find Bottom Left Value (medium) | Left side view → last element. Or BFS right-to-left, last popped | ||
| 3. Vertical Order Traversal (hard) | BFS + TreeMap<col, list>. Sort by row then val for same position | ||
| 4. Boundary Traversal (medium) | Left boundary + leaves + right boundary (reversed) |
7.5 Path Problems (Root-to-Leaf & Any Path)
💡 Signal: “root to leaf”, “path sum”, “all paths”, “maximum path sum”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Binary Tree Paths (easy) | DFS, build string, add at leaf | ||
| 2. Path Sum (easy) | Subtract node val from target, check == 0 at leaf | ||
| 3. Path Sum II (medium) | Same + backtracking to collect all paths | ||
| 4. Path Sum III (medium) | Prefix sum + hashmap. Any node to any node downward | ||
| 5. Sum Root to Leaf Numbers (medium) | currNum = currNum * 10 + node.val. Sum at leaves | ||
| 6. Binary Tree Maximum Path Sum (hard) | At each node: max(left,0) + val + max(right,0). Return one side | ||
| 7. Smallest String from Leaf (medium) | Build string leaf→root, compare lexicographically | ||
| 8. Pseudo-Palindromic Paths (medium) | XOR bitmask for digit frequencies. At leaf check at most 1 bit set | ||
| 9. Insufficient Nodes (medium) | Post-order. If all paths through node < limit, remove it |
7.6 Lowest Common Ancestor (LCA)
💡 Signal: “lowest common ancestor”, “LCA”, “common parent”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. LCA of Binary Tree (medium) | If left & right both non-null → root is LCA. Else return non-null | ||
| 2. LCA of BST (medium) | Use BST property: if both < root go left, both > root go right | ||
| 3. LCA of Deepest Leaves (medium) | Track depth. LCA is where left depth right depth max depth | ||
| 4. Max Diff Node & Ancestor (medium) | Pass min/max down. At leaf compute max−min | ||
| 5. Kth Ancestor (hard) | Binary lifting: parent[i][j] = parent[parent[i][j-1]][j-1] |
7.7 BST-Specific Problems
💡 Signal: “BST”, “binary search tree”, “inorder sorted”, “validate BST”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Validate BST (medium) | Pass (min, max) range. Or check inorder is strictly increasing | ||
| 2. Search in BST (easy) | val < root → go left, val > root → go right | ||
| 3. Insert into BST (medium) | Find null spot using BST property. Insert there | ||
| 4. Delete Node in BST (medium) | 3 cases: leaf, one child, two children (replace with successor) | ||
| 5. Kth Smallest in BST (medium) | Inorder traversal, return kth element | ||
| 6. Convert BST to Greater Tree (medium) | Reverse inorder (right→root→left) with running sum | ||
| 7. BST to Greater Sum Tree (medium) | Same as Convert BST to Greater Tree | ||
| 8. Trim a BST (medium) | If val < low, return trim(right). If val > high, return trim(left) | ||
| 9. Range Sum of BST (easy) | Only recurse into valid range branches | ||
| 10. Two Sum IV BST (easy) | Inorder to sorted array + two pointers. Or DFS + HashSet | ||
| 11. All Elements in Two BSTs (medium) | Inorder both trees → merge two sorted lists | ||
| 12. Min Absolute Diff BST (easy) | Inorder traversal, track prev node, min diff = curr − prev | ||
| 13. Increasing Order Search Tree (easy) | Inorder traversal, relink nodes as right-only chain | ||
| 14. Recover BST (medium) | Inorder: find two swapped nodes (first & second violation) |
7.8 Tree Construction
💡 Signal: “construct tree from”, “build BST”, “convert sorted array”, “serialize”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. From Preorder & Inorder (medium) | Preorder[0]=root. Find root in inorder → splits left/right | ||
| 2. From Inorder & Postorder (medium) | Postorder[last]=root. Same split logic | ||
| 3. From Preorder & Postorder (medium) | Preorder[1]=left root. Find in postorder for size | ||
| 4. Sorted Array to BST (easy) | Mid element = root. Recurse on left & right halves | ||
| 5. Sorted List to BST (medium) | Find mid with slow/fast pointer. Or simulate inorder | ||
| 6. BST from Preorder (medium) | Use upper bound. O(N) with global index | ||
| 7. Serialize & Deserialize BT (hard) | Preorder with null markers. Use queue for deserialize | ||
| 8. Serialize & Deserialize BST (medium) | No null markers needed — use BST bounds to reconstruct | ||
| 9. Unique BSTs II (medium) | For each root i, combine all left trees × all right trees | ||
| 10. Unique BSTs (Count) (medium) | Catalan number. DP: dp[n] = Σ dp[i-1] * dp[n-i] |
7.9 Node Distance & Relations
💡 Signal: “distance between nodes”, “all nodes at distance k”, “cousins”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. All Nodes Distance K (medium) | Build parent map → BFS from target node k levels | ||
| 2. Cousins in Binary Tree (easy) | Same depth, different parents. BFS tracking parent & depth | ||
| 3. Sum of Distances in Tree (hard) | Two-pass DFS: root answer → re-root to compute all nodes | ||
| 4. Min Distance Between BST Nodes (easy) | Inorder, track prev node diff. Same as Min Absolute Diff |
7.10 Leaves, Deletion & Misc
💡 Signal: “leaf nodes”, “delete node”, “flatten”, “count nodes”, “completeness”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Sum of Left Leaves (easy) | Check if left child is leaf: left!=null && left.left==null && left.right==null | ||
| 2. Leaf-Similar Trees (easy) | Collect leaf sequences of both trees, compare | ||
| 3. Deepest Leaves Sum (medium) | BFS: sum of last level. Or DFS tracking max depth | ||
| 4. Delete Leaves with Value (medium) | Post-order. If leaf matches target, return null. Repeat | ||
| 5. Delete Nodes Return Forest (medium) | Post-order. If node deleted, its children become new roots | ||
| 6. Flatten BT to Linked List (medium) | Reverse postorder (right→left→root). Or Morris threading | ||
| 7. Count Complete Tree Nodes (medium) | O(log²n): if left height == right height → 2^h − 1. Else recurse | ||
| 8. Check Completeness (medium) | BFS. Once a null is seen, no more non-null nodes should appear | ||
| 9. Count Good Nodes (medium) | DFS passing maxSoFar. If node.val >= maxSoFar, it’s good | ||
| 10. Good Leaf Nodes Pairs (medium) | Post-order return distances. Combine left & right distances | ||
| 11. Smallest Subtree Deepest (medium) | Same as LCA of deepest leaves | ||
| 12. Flip Equivalent Trees (medium) | Recursively check: same or swapped children | ||
| 13. Validate Binary Tree Nodes (medium) | Exactly one root (no parent), no cycles, all nodes connected |