BFS, DFS & Dijkstra

Three traversals, one job: visit every reachable state and, on the way, answer a question about paths or solutions. BFS spreads outward in rings like a stone dropped in water and reads off the fewest number of steps. DFS plunges down one branch at a time and — with backtracking — enumerates every subset, permutation, and combination. Dijkstra is BFS that swaps the plain queue for a priority queue so it can respect edge weights. This session builds all three from a single mental model, a search tree, and walks the interview problems each one owns — from level-order printing to graph coloring to the entire backtracking family.

One Search Tree, Three Traversals

Every problem in this session is exhaustive search: you are walking a (possibly implicit) tree or graph and either reading off a shortest distance or collecting all possible solutions. The three tools differ only in the order they visit states and the data structure that dictates that order.

• BFS thinks in neighbours and steps. Drop a stone in water: the ripple reaches everything one hop away, then two hops away, then three. That expanding-ring order is exactly why BFS finds the shortest path in an unweighted graph — the first time you touch a node, you touched it by the fewest edges.
• DFS commits to one branch and rides it to the bottom before backing up. Preorder is the traversal that most resembles raw recursion — do the node, then recurse left, then recurse right. When the goal is "list every arrangement", DFS with backtracking is the natural fit.
• Dijkstra is best-first search: a weighted BFS that always expands the closest unfinished node next. Replace the FIFO queue with a priority queue and BFS becomes Dijkstra; make every weight equal and Dijkstra becomes BFS again.

A concrete anchor: walking a binary tree top-to-bottom, left-to-right is BFS. Keep that image — half the problems below are just that walk with a twist.

BFS: The Level-Order Template

The whole of BFS is a queue and a loop. You seed the queue with the start node, then repeatedly poll a node and offer its unvisited neighbours. The one idea that elevates it from "flat traversal" to "level-order output" is to freeze the queue's size at the start of each level: everything currently in the queue belongs to the current level, so a single for loop over that count drains exactly one layer.

public void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();          // freeze this level's width
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            // visit node.val here — this is level `depth`
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        // one full level processed — bump depth, close a sub-list, etc.
    }
}

There are three classic ways to know where a level ends: run two queues and swap them each round, insert a sentinel (a null marker or "next" pointer between levels), or the cleanest of the three — the per-level size above. Prefer the size trick; it needs no extra allocation and never confuses the sentinel with real data.

Level-Order Variations

Four problems ride the same template, each changing exactly one thing.

LC 102 — Binary Tree Level Order Traversal

The template verbatim: open a fresh sub-list at the top of each level, fill it inside the for loop, append it after. There is also a slick DFS alternative: preorder-recurse carrying a height argument, and when height >= ans.size() create the row for that depth before appending. Preorder visits each row's leftmost node first, so the rows fill in the right order — a nice demonstration that "level order" does not strictly require BFS.

LC 107 — Level Order II (bottom-up)

Identical to LC 102, then Collections.reverse(ans). Do not overthink it: solve the problem you know and flip the result.

LC 314 — Binary Tree Vertical Order Traversal

Assign the root column 0, a left child col - 1, a right child col + 1, and BFS while carrying a parallel queue of columns. Bucket each value into a HashMap<Integer, List> keyed by column, track minCol and maxCol as you go, then emit columns left to right. BFS (not DFS) matters here: it guarantees nodes in the same column come out top-to-bottom.

LC 103 — Zigzag Level Order Traversal

Two honest options. The lazy one: run LC 102 and Collections.reverse the odd rows (or insert into each row at the head with list.add(0, val)). The slick one: drive a Deque and alternate ends — on left-to-right rows removeFirst and add children to the tail; on right-to-left rows removeLast and add children to the head. Flip a boolean each level. Both are O(n); the deque version is the one interviewers enjoy watching you reason through.

When BFS Validates: Complete Trees & Bipartite Graphs

BFS is not only for shortest paths — its level-by-level discipline makes it a natural consistency checker.

LC 958 — Check Completeness of a Binary Tree

A complete tree fills every level left-to-right with no gaps. Do a level-order traversal that includes the null children, and keep a metNull flag: the moment you have seen a null, any subsequent real node proves the tree is not complete. One boolean and one pass. (A tidier variant checks each node's two children per level and trips the same flag whenever a missing child is followed by a present one.)

LC 785 — Is Graph Bipartite?

A graph is bipartite iff you can two-color it so no edge joins same-colored nodes. BFS the graph painting every neighbour the opposite color of the current node — black's neighbours go white, white's go black. If you ever try to paint a node a color it already contradicts, it is not bipartite. Two details the notes flag: keep a visited/color array to detect the conflict across cycles, and loop over every node as a potential start because the graph may be disconnected.

Dijkstra: BFS With a Priority Queue

Dijkstra finds the shortest path from one source to every node in a weighted graph. Note the "every" — even if you only care about A→B, the algorithm computes A→all as a side effect, because it cannot know it has the final answer for B until every shorter route has been ruled out. The engine is a min-heap keyed by distance-so-far: repeatedly pop the closest unfinished node, mark it done, and relax its edges (if going through it beats a neighbour's best known distance, update it).

// graph[u] = list of {neighbour, weight}; returns dist[] from src
public int[] dijkstra(List<int[]>[] graph, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // heap of {node, distSoFar}, ordered by distance
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0});
    boolean[] visited = new boolean[n];

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0];
        if (visited[u]) continue;      // stale entry — already finalized
        visited[u] = true;

        for (int[] edge : graph[u]) {   // edge = {v, weight}
            int v = edge[0], w = edge[1];
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;               // relax
                pq.offer(new int[]{v, dist[v]}); // "lazy" decrease-key
            }
        }
    }
    return dist;
}

Java's PriorityQueue has no decreaseKey, so we do not update entries in place — we simply re-insert a node with its improved distance and skip any node we pop that is already visited. That if (visited[u]) continue; line is the whole trick: it discards the stale, larger-distance copies. To reconstruct the actual path, keep a prev map alongside dist and walk it backwards from the target.

Kth Smallest in a Sorted Matrix (LC 378)

A matrix whose rows and columns are both sorted is a weighted-search playground. The smallest element is [0][0]; from any cell [i][j] the next candidates are [i+1][j] and [i][j+1]. Push [0][0] into a min-heap, then pop-and-expand; the k-th pop is the answer. Because two paths can reach the same cell, guard with a HashSet so each cell is pushed once.

public int kthSmallest(int[][] matrix, int k) {
    int cols = matrix[0].length, max = matrix.length * cols;
    Set<Integer> seen = new HashSet<>();

    // store flattened index; order by the value it points at
    PriorityQueue<Integer> pq = new PriorityQueue<>(
        (a, b) -> matrix[a / cols][a % cols] - matrix[b / cols][b % cols]);

    pq.offer(0); seen.add(0);
    for (int count = 0; count < k - 1; count++) {
        int idx = pq.poll();
        int down = idx + cols, right = idx + 1;
        if (down < max && seen.add(down))  pq.offer(down);
        // right must stay on the same row (idx % cols != cols-1)
        if (idx % cols != cols - 1 && seen.add(right)) pq.offer(right);
    }
    int idx = pq.poll();
    return matrix[idx / cols][idx % cols];
}

The flattening trick — index = i * cols + j, then i = index / cols, j = index % cols — lets a single int stand in for a coordinate pair, so a plain HashSet<Integer> can dedup cells (a raw [i, j] pair is not hashable without a wrapper class). At most three cells enter the heap per pop, so the heap stays around size k: O(k log k) time, O(k) space. It is Dijkstra's expand-and-dedup shape applied to an implicit grid.

DFS & Backtracking: The Recursion-Tree Framework

DFS comes in preorder, inorder, and postorder; preorder is the one that reads like recursion. But the payoff of DFS in interviews is backtracking — the pattern for "return all subsets / combinations / permutations". Before writing a line, draw the recursion tree and answer three questions:

1. How many levels, and what does each mean? Top-to-bottom is the recursion depth.
2. How many branches per level? Left-to-right is the for loop.
3. Where is the answer? At every node, or only at the leaves?

The skeleton is always choose → recurse → un-choose: append a candidate, recurse, then remove it. Why the un-choose? Because the whole recursion shares a single mutable buffer — one StringBuilder, one List. As one candidate correctly put it: with a shared StringBuilder you mutate the same object, so you must delete the last character before trying the next branch; with immutable str + c concatenation every call gets a fresh copy and no cleanup is needed. The delete line exists solely because there is exactly one buffer for the entire process.

Subsets: Two Shapes of the Same Tree (LC 78)

Given distinct numbers, return the power set. Two DFS shapes, both O(2ⁿ), both worth knowing because they generalize differently.

Shape 1 — pick-from-here, answer at every node

At each node, the loop chooses the next element from index … n-1; advancing to i + 1 means "never look back", which is what makes each subset appear once. Every node on the tree is a valid subset, so res.add(...) sits at the top of the call — this is the classic template.

private void dfs(int[] nums, int index,
                 List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));   // every node is an answer → deep copy
    // base case (index out of range) returns implicitly
    for (int i = index; i < nums.length; i++) {
        path.add(nums[i]);                 // choose nums[i]
        dfs(nums, i + 1, path, res);       // recurse from i+1 — never look back
        path.remove(path.size() - 1);   // un-choose (backtrack)
    }
}

Shape 2 — take-or-skip, answer at the leaf

A strict binary tree: at index i, branch left "include nums[i]", branch right "exclude it". Only the leaves (index past the end) are complete subsets, so res.add(...) lives in the base case. Even if you write the two branches in the other order, you still must un-choose after the include branch — backtracking demands the buffer be restored. (BFS can build subsets too, growing every partial subset one element at a time layer by layer, but the two DFS shapes are what you will code under time pressure.)

The Combination Family (LC 77 / 39 / 40 / 216 / 22)

Combinations are subsets with a size or sum constraint. The template barely changes; what changes is the loop's start index and the base case.

LC 77 — Combinations

Pick k numbers from 1 … n. Advance the loop with i + 1 (order does not matter, so never reuse a smaller index) and record when path.size() == k.

LC 39 — Combination Sum

Each number may be reused unlimited times, so recurse with i (not i + 1) to allow re-picking the same element. Prune when remain < 0, collect when remain == 0.

LC 40 — Combination Sum II

Each number used once and the input has duplicates. Two edits: recurse with i + 1, and sort first, then skip duplicate siblings so two equal values at the same tree level do not spawn identical branches.

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);                // duplicates become adjacent
    backtrack(res, new ArrayList<>(), nums, target, 0);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> path,
                       int[] nums, int remain, int start) {
    if (remain < 0) return;
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }

    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicate siblings
        path.add(nums[i]);
        backtrack(res, path, nums, remain - nums[i], i + 1); // i+1: use each once
        path.remove(path.size() - 1);
    }
}

LC 216 — Combination Sum III

Use only the digits 1 … 9, each at most once, exactly k of them summing to n. It is LC 77 fused with a running sum: recurse with i + 1 over the fixed pool 1–9, and accept when both path.size() == k and the remainder hits zero.

LC 22 — Generate Parentheses

For n pairs there are 2n slots; each level branches on "add (" or "add )". Brute force would generate all strings and filter, but the elegant version prunes: you may open a bracket only while open < n, and close one only while close < open. Those two guards make every string generated valid.

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    helper(res, new StringBuilder(), 0, 0, n);
    return res;
}

private void helper(List<String> res, StringBuilder sb,
                    int open, int close, int n) {
    if (open == n && close == n) {
        res.add(sb.toString());
        return;
    }
    if (open < n) {                       // can always open another '('
        sb.append('(');
        helper(res, sb, open + 1, close, n);
        sb.setLength(sb.length() - 1); // backtrack the one buffer
    }
    if (close < open) {                   // only close what's open
        sb.append(')');
        helper(res, sb, open, close + 1, n);
        sb.setLength(sb.length() - 1);
    }
}

Permutations & Coin Change (LC 46 / 47 / 322)

LC 46 — Permutations

Order matters and every element is used exactly once, so the tree has depth n and each level may pick any number not yet in the path. The answer lives at the leaves (path.size() == n). The simplest guard is path.contains(nums[i]); a length-preserving alternative swaps elements in place.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), nums);
    return res;
}

private void backtrack(List<List<Integer>> res,
                       List<Integer> path, int[] nums) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path)); // answer at the leaf
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (path.contains(nums[i])) continue; // skip numbers already placed
        path.add(nums[i]);
        backtrack(res, path, nums);
        path.remove(path.size() - 1);
    }
}

LC 47 — Permutations II

Duplicates in the input. Sort, carry a used[] array, and add the guard if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;. The !used[i-1] clause forces equal values to be consumed strictly left-to-right, which collapses the mirror-image branches that would otherwise produce duplicate permutations.

LC 322 — Coin Change

Fewest coins to make an amount. The notes sketch two recursion trees: an n-ary tree where each node adds one coin of some denomination, and a leaner one with one level per denomination whose branches are "use this coin 0, 1, 2, … times". Pure DFS is exponential; memoize it top-down, or go bottom-up with dp[i] = min(dp[i], dp[i - coin] + 1). A classic trap the notes call out: initialize the DP array with amount + 1 as the "infinity" sentinel rather than Integer.MAX_VALUE — otherwise the + 1 in the transition overflows to the most negative int and quietly corrupts the answer.

Problem Checklist