Recursion & Divide and Conquer

Recursion is where "I understand the idea" and "I can write it under pressure" diverge the fastest. The idea is one sentence — a function solves a big instance by calling itself on smaller ones — but the interview failures are specific: a base case that forgets to return, an update that mysteriously doesn't persist across calls, a stack that overflows because two methods keep calling each other in a circle. This session builds the mental model once and then spends it across two arenas: divide-and-conquer on arrays and grids (merge sort, quick select, N-Queens, spiral matrix) and recursion on trees, where recursion isn't a technique you reach for — it's the only way the data structure knows how to be traversed.

The Shape of a Recursive Solution

Before any specific problem, the session pins down the anatomy that every recursion shares. Two failure modes bracket the whole topic. Direct self-call without a shrinking argument overflows the stack — the classic infinite recursion. Indirect recursion is sneakier: A() calls B(), B() calls C(), C() calls A() — a cycle that also overflows, but is far harder to spot in a review. Every recursion needs a reduction that provably moves toward a base case.

There are two reduction shapes, and they map cleanly onto complexity:

• Linear reduction — f(n) depends on f(n-1) or f(n-2). You peel one item per level, so the recursion is O(n) deep. Fibonacci, climbing stairs (LC 70), and jump game (LC 55) are the canonical shapes — each state reaches back one or two steps. (When those overlapping calls explode, memoization turns them into DP — that is the bridge into the next two sessions.)
• Divide and conquer — f(n) depends on f(n/2). You halve the problem each level, so the tree is only O(log n) deep. Binary search is the purest example: it throws away half the space and recurses on one side.

The other two rules are the ones people actually get wrong. The base case must return. A base case that computes the right thing but forgets to return it silently falls through and corrupts the answer — put the base case at the top of a private helper. Corner cases belong in the public method. Null input, empty arrays, single nodes — check them once in the public wrapper, then hand the helper clean, invariant-preserving input. This separation keeps the recursive core small and honest.

Divide and Conquer on Arrays: Sort, Search, and the Recursion Tree

The array classics are where divide and conquer earns its name. Merge sort splits the array in half, recursively sorts each half, and merges two sorted halves in linear time. Quick sort partitions around a pivot, then recurses on both sides. Their recursion trees look identical — log n levels, O(n) work per level — which is exactly the master-theorem intuition the session leans on rather than the formula: draw the tree, sum the work per level, multiply by the number of levels.

That summation is worth doing by hand at least once, because it demystifies where the complexities come from:

merge / quick sort:   n  +  2·(n/2)  +  4·(n/4)  + ...   =  n per level × log n levels  =  O(n log n)

tree height getDepth: 1  +  2  +  4  + ... + 2^(logn-1)  =  2^logn                     =  O(n)

N-Queens validate():  n  +  n^2 +  n^3 + ... + n^(n-1)   =  O(n^(n+1))   // note: NOT O(n^n)

Quick select is quick sort's leaner cousin and the one interviewers love: to find the k-th smallest element, partition once, then recurse into only the side that contains k. Discarding the other half collapses the expected cost from O(n log n) to O(n) — the same "throw away half" instinct as binary search, applied to selection. And binary search itself, viewed through this lens, is just divide and conquer that always recurses on exactly one child and does O(1) work per level. The session frames binary search as "the flat version of DFS," which is the connective tissue between this session and the tree material below.

Backtracking on 2D Boards: N-Queens & Sudoku

Move from 1D to 2D and recursion becomes backtracking: try a choice, recurse, and undo the choice on the way back out so the next branch starts clean. LC 51 N-Queens is the archetype — place one queen per column (or row), and at each step keep only the placements that don't conflict with anything already down. The elegant part is the conflict test. Because you fill left to right, a new queen can only clash with columns already placed, and only along three lines: same row, the ↘ diagonal, and the ↗ diagonal.

The diagonal identity is the trick worth memorizing: on a ↘ diagonal, row + col is constant; on a ↗ diagonal, row - col is constant. That turns an O(n) board scan into three O(1) set lookups. LC 52 N-Queens II only counts solutions, so you don't even materialize the board — three HashSets carry all the state you need:

class Solution {
    public int totalNQueens(int n) {
        Set<Integer> cols = new HashSet<>();   // occupied columns
        Set<Integer> diag = new HashSet<>();   // row - col  (↘, 135°)
        Set<Integer> anti = new HashSet<>();   // row + col  (↗, 45°)
        return dfs(cols, diag, anti, n, 0, 0);
    }

    private int dfs(Set<Integer> cols, Set<Integer> diag,
                    Set<Integer> anti, int n, int row, int count) {
        for (int col = 0; col < n; col++) {
            if (cols.contains(col))       continue;
            if (diag.contains(row - col)) continue;   // same ↘ diagonal
            if (anti.contains(row + col)) continue;   // same ↗ diagonal

            if (row == n - 1) {
                count++;                              // last row filled → one full solution
            } else {
                cols.add(col); diag.add(row - col); anti.add(row + col);
                count = dfs(cols, diag, anti, n, row + 1, count);
                cols.remove(col); diag.remove(row - col); anti.remove(row + col);
            }
        }
        return count;
    }
}

Note the honest complexity: N-Queens is O(n^(n+1)) if validate is O(1), and the session flags the easy misread — n^(n+1) is not n^n. The sets don't change the exponential nature; they just shrink the constant and clean up the branch test.

LC 36 Valid Sudoku contributes a second reusable pattern: traversing a 3×3 block with a single index. The move that's worth committing to memory is squareRow = 3 * (i / 3), squareCol = 3 * (i % 3) to pick a block's top-left corner, then board[squareRow + j/3][squareCol + j%3] to walk its nine cells — % steps horizontally, / drops a row. LC 37 Sudoku Solver then wraps that validity check in the same backtracking loop as N-Queens: for the current empty cell, try '1' through '9', place one if valid, recurse, and on failure erase it and try the next. Place → recurse → un-place is the backtracking heartbeat.

Spiral Matrix: Peeling Layers Recursively

LC 54 Spiral Matrix and LC 59 Spiral Matrix II read a matrix in a clockwise spiral, and the cleanest framing is recursive: print the outer ring, then recurse on the sub-matrix inside it. Each call handles four edges — top row left-to-right, right column top-to-bottom, bottom row right-to-left, left column bottom-to-top — then calls itself with the dimensions shrunk by two and the offset bumped by one. The two base cases that catch beginners are the degenerate rings: a single remaining row (m == 1) or single column (n == 1), which must be printed without double-counting the corner.

A few notes from the session that separate a rehearsed answer from a shaky one: it handles non-square matrices (track m and n independently, not one side length), it uses no extra space beyond the output list, and the same logic rewrites trivially as a while loop (m -= 2; n -= 2; offset++) for anyone who prefers iteration. For the generation variant, spotting the coordinate-to-value formula matrix[i][j] = i * n + j is what makes the fill loop fall out. The broader lesson connects back to the top of the session: a spiral is just divide and conquer where "divide" means "strip off the boundary layer."

Why Trees Are Recursion Incarnate

Here the session pivots, and the tone changes. On arrays you choose recursion; on trees you can barely avoid it, because a tree is defined recursively — a node is a value plus a left subtree and a right subtree, each of which is itself a tree. The base case writes itself: the null beneath a leaf. And nearly every tree problem fits one three-line template:

1. Ask the children — recurse into root.left and root.right.
2. Do the work at this level — combine the two answers, update any running state.
3. Return one value upward — the summary this node hands its parent.

The session calls this the bottom-up pattern: information flows from the leaves up, and no node needs to carry context down from above. That's the natural fit for anything that looks like DP on a tree. The opposite direction — top-down, where a node passes context down to its children — shows up too (validate-BST carries min/max bounds down; path-sum carries a running total down), and knowing which direction a problem wants is half the battle. A quick tell from the notes: the reverse-everything drill (reverse an array, a string, a list, an integer, its bits, or a tree) is really the same recursion wearing six costumes — swap the two children, recurse, done.

Height, Balance, and the Sentinel Trick

Computing a tree's height is the template at its simplest: 1 + max(height(left), height(right)), base case 0 at null, O(n) total. The instructive problem is LC 110 Balanced Binary Tree, because the obvious solution is quietly quadratic. If you write isBalanced to call a separate getDepth at every node, you pay O(n) per node across O(n) nodes — O(n log n) on a balanced tree, O(n²) in the worst case. Interviewers wait to see whether you notice.

The fix is a pattern that pays off across dozens of tree problems: make the post-order return carry extra information. Redefine the height function to return -1 as a sentinel meaning "a subtree below me is already unbalanced." The moment either child reports -1, or the height gap exceeds 1, you return -1 and the failure races straight to the root — one pass, O(n):

// getDepth doubles as the balance check: -1 means "unbalanced below me"
private int getDepth(TreeNode root) {
    if (root == null) return 0;
    int left  = getDepth(root.left);
    int right = getDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1)
        return -1;                       // short-circuit the whole subtree
    return 1 + Math.max(left, right);
}

public boolean isBalanced(TreeNode root) {
    return getDepth(root) != -1;
}

The same "store an answer instead of recomputing it" idea generalizes. If a problem asks for the number of nodes in every subtree in O(1), you can't traverse on demand — you precompute and cache it in a field on the node (TreeNode.leftSubtreeCount), filled during one post-order pass. LC 222 Count Complete Tree Nodes is the same counting recursion (left + right + 1), and stashing the left count in a field as you go is exactly how you'd support later O(1) subtree-size queries. Trees are objects; an object can hold a cache.

Carrying State Through Recursion: Global vs Wrapper

This is the single most transferable idea in the session, and the one that trips up strong candidates who've only ever recursed with return values. Consider: find the node whose left and right subtrees differ most in node count. The count is bottom-up (the height template again), but the answer — which node won — has to survive the entire traversal. There are two ways to keep it.

Option 1: a variable outside the recursion. A class field — static on the class, or an instance field on a new Solution() — that every frame reads and writes. Simple, and fine for single-threaded interview code.

Option 2: pass a wrapper argument. And here's the trap the session drills: you cannot pass a bare int. Java is pass-by-value — the argument copies the value sitting on the stack, so each frame gets its own private max; updates in a child never reach the parent. The fix is to pass something whose reference is copied but whose contents are shared: an int[1], or a TreeNode[1] when the thing you want to remember is a node:

int[] max = new int[1];              // a heap object → every frame shares it
TreeNode[] maxNode = new TreeNode[1];

private int countNodes(TreeNode root, int[] max, TreeNode[] maxNode) {
    if (root == null) return 0;
    int left  = countNodes(root.left,  max, maxNode);
    int right = countNodes(root.right, max, maxNode);
    int diff = Math.abs(left - right);
    if (diff > max[0]) {              // a plain `int max` argument would NOT persist
        max[0] = diff;
        maxNode[0] = root;
    }
    return left + right + 1;          // post-order: children counted before parent
}

The session's own phrasing is worth keeping: you wrap the thing you want at one level higher than it lives. Want to mutate an int? Wrap it in an int[]. Want to reassign which TreeNode you're pointing at? A TreeNode is already an object, but reassigning the local doesn't propagate — so wrap it in a TreeNode[]. The array is the shared mailbox; every frame drops mail in the same box.

Lowest Common Ancestor, Four Ways

LC 236 Lowest Common Ancestor of a Binary Tree is the cleanest demonstration of "find the answer inside the return values." The recursion asks each subtree whether it contains p or q. The base case returns the node itself if it is p, q, or null. Then the combine step is pure logic: if only one side came back non-null, the answer is up there; if both sides came back non-null, the current node is where p and q split — the LCA.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left  = lowestCommonAncestor(root.left,  p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null)  return right;   // both targets live on the right
    if (right == null) return left;    // both targets live on the left
    return root;                        // p and q split here → LCA
}

The session then spins the same problem four ways, each a small variation:

• With parent pointers — walk up from p marking visited nodes, then walk up from q until you hit a marked one. No full traversal needed.
• LC 235, LCA in a BST — the ordering does the work. The LCA's value must sit between p.val and q.val, so descend from the root: go right if both targets are larger, left if both smaller, and the first node that lands between them is the answer. Trivially iterative, O(h).
• N nodes, not two — identical structure, just a longer base case (return non-null if the node is any of the targets) and the same "return the non-null side, else the node where they merge."
• K-ary trees — instead of left/right, count how many children returned non-null: zero → return null, one → bubble that one up, more than one → this node is the LCA.

Path Sums and the Maximum Path

The path family is where the "carry down" and "bubble up" directions meet in one problem set. LC 112 Path Sum (does a root-to-leaf path hit the target?) and LC 113 Path Sum II (return all of them) carry a shrinking remaining-sum down the tree, and LC 113 adds a classic backtracking list — cur.add(root.val) on the way in, cur.remove(cur.size()-1) on the way out. LC 437 Path Sum III raises the bar: the path can start and end anywhere as long as it goes downward. The brute force fixes each node as a start and searches down — O(n²) worst case, O(n log n) balanced — but the elegant answer is a prefix-sum HashMap, the tree cousin of two-sum: map each running prefix sum to how many times it's occurred, and at each node check for prefixSum - target. One pass, O(n), with an add-on-entry / remove-on-exit backtrack to keep the map path-local.

The crown jewel is LC 124 Binary Tree Maximum Path Sum, and the session's advice is exactly right: it's too hard to see whole, so simplify. Enumerate the path shapes — leaf-to-root, node-to-root, leaf-to-leaf — and build up. Two insights crystallize the solution. First, a subtree that contributes a negative sum should simply be dropped, so you clamp each child's contribution with Math.max(0, child). Second, distinguish the two things a node computes: the best path that turns at this node (left + right + val, which updates a global maximum) versus the best path it can hand upward (max(left, right) + val, because a parent can only extend through one child):

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left  = Math.max(0, dfs(root.left));    // drop a negative branch
        int right = Math.max(0, dfs(root.right));
        max = Math.max(max, left + right + root.val);   // path that turns at root
        return Math.max(left, right) + root.val;        // path that continues upward
    }
}

The opposite information direction shows up in LC 98 Validate BST: correctness isn't a local check (comparing a node only to its immediate children misses violations from far-away ancestors), so you carry a (min, max) bound down the tree, tightening it at each step — go left and the current value becomes the new upper bound, go right and it becomes the new lower bound. Use long bounds to survive Integer.MIN_VALUE/MAX_VALUE node values. Same tree, opposite flow: LC 124 bubbles sums up, LC 98 pushes constraints down.

Rebuilding Trees: Serialize & Construct

The finale reframes divide and conquer as reconstruction: instead of splitting a problem, you split the input and rebuild the structure. LC 297 Serialize and Deserialize Binary Tree asks how a tree lives in memory and travels over a wire. The clean encoding is a preorder walk that writes a sentinel ("X") for every null; deserialization reads that stream through a queue, and because preorder emits the root first, buildTree pops a value, then recursively builds left and right — the recursion mirrors the serialization exactly. (The session also notes the theory: a single traversal plus nulls is enough to be unambiguous, and so is any inorder + preorder or inorder + postorder pairing.)

That pairing is LC 105 Construct Binary Tree from Preorder and Inorder. preorder[0] is always the root; find it inside inorder and everything to its left is the left subtree, everything to its right is the right subtree. Recurse on the two halves with adjusted index windows:

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(0, 0, inorder.length - 1, preorder, inorder);
}

private TreeNode helper(int preStart, int inStart, int inEnd,
                        int[] preorder, int[] inorder) {
    if (preStart > preorder.length - 1 || inStart > inEnd) return null;

    TreeNode root = new TreeNode(preorder[preStart]);   // preorder head is the root
    int inIndex = inStart;
    for (int i = inStart; i <= inEnd; i++)
        if (inorder[i] == root.val) inIndex = i;        // split point in inorder

    root.left  = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
    root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
    return root;
}

The linear scan for the split makes this O(n log n); a value→index HashMap drops it to O(n). LC 106 is the mirror image — postorder[last] is the root, and you build right before left. Level-order + inorder works by the same recipe: level[0] is the root, split inorder around it, then filter the level sequence into each side.

Two more reconstructions round out the session, both "pick the middle as the root." LC 108 Convert Sorted Array to BST takes mid as the root and recurses on the halves — a height-balanced BST for free (and the notes flag the nuance: a balanced BST isn't unique, but a complete one, with the last level pushed left, is). LC 109 Convert Sorted List to BST is the same idea over a linked list, where you can't index — so a fast/slow pointer finds the middle node in O(n) per level. The other tree-restructuring cousins live here too: LC 114 Flatten Binary Tree to Linked List (a reverse-preorder walk threading each node's right pointer, with left nulled) and the in-place LC 426 tree-to-doubly-linked-list, which exploits the fact that a TreeNode already has two pointers — reuse left/right as prev/next and thread them during an inorder walk, no extra space.

Problem Checklist