Recursive Thinking
Learn to break big problems into smaller ones
The leap from ‘I can use data structures’ to ‘I can solve novel problems’ happens when you internalize recursion and tree thinking. Trees are the perfect training ground because every problem naturally decomposes into subproblems on left and right children.
For every tree problem, before coding, write the recurrence in words: ‘The answer for this node depends on ___ from the left child and ___ from the right child.’
🌳Binary Trees
Trees teach you to think recursively. The pattern ‘process this node using results from children’ is the same pattern used in DP, divide & conquer, and segment trees.
The simplest recursive tree transformation. Swap left and right, recurse.
1 + max(left_depth, right_depth). This IS the recursive template.
Key insight: the answer might not pass through the root. Track a global max.
Use the BST property to decide which subtree to explore.
In-order traversal gives sorted order. Can you do it iteratively with a stack?
Like diameter but with values. Return one-side max to parent, track global two-side max.
🔙Backtracking
Backtracking is ‘structured brute force’ — try a choice, recurse, undo the choice. It’s the foundation for bitmask DP (which is just memoized backtracking) and teaches you to think about state space.
The canonical backtracking template. Include or exclude each element.
Backtracking with a ‘used’ set. Draw the decision tree.
Unbounded choices. How do you avoid duplicates?
2D grid backtracking. Mark visited, explore 4 directions, unmark.
Row-by-row placement with column/diagonal constraint checking. Classic.
Backtrack on where to cut. Precompute palindrome checks with DP.
🕸️Graphs: BFS & DFS
Graphs generalize trees (trees are just acyclic connected graphs). BFS/DFS are the workhorses — every advanced graph algorithm builds on them.
Flood fill with DFS. The grid IS the graph — each cell is a node.
BFS/DFS with a visited HashMap that maps old → new nodes.
Cycle detection in directed graph. Both DFS (3-color) and Kahn’s BFS work.
Topological sort — output the ordering, not just detect cycles.
Multi-source BFS. All rotten oranges start in the queue simultaneously.
BFS on an implicit graph. Each word is a node, edges connect words differing by one letter.