Trees and Graphs · Backend Study Library

Almost every tree or graph problem is one traversal (DFS or BFS) plus a single decision repeated at every node: what state do I pass down, and what value do I return up. Get the traversal skeleton and that decision right and the rest is bookkeeping.

Series map: 00 playbook · 01 two pointers & sliding window · 02 binary search, stacks & intervals · 03 trees & graphs (this file) · 04 recursion & backtracking · 05 dynamic programming · 06 staff+ practical & OOD. Companion (non-series): data-structures-java-kotlin-study-guide.md — reach there for why a HashMap / ArrayDeque / PriorityQueue / disjoint-set behaves as it does (buckets, boxing, cache locality, α(n) amortization). This guide uses those structures as tools and spends its words on the algorithm.

The mental model#

A tree is a connected acyclic graph: n nodes, n−1 edges, exactly one path between any two nodes, no cycles. A general graph adds cycles and disconnection. Every problem in this guide is a traversal — visit nodes in some order — where at each node you decide two things: the state you carry down into children (an accumulator, bounds, a path), and the value you fold up from children (a height, a sum, a boolean, a subtree answer). Pick the traversal by what you need; pick the down/up state by what the answer depends on.

Two consequences drive every decision:

Trees have no cycles, so recursion is clean — no visited set, O(h) stack depth. Graphs have cycles, so you MUST track visited or you loop forever. This single fact is why "clone a tree" is five lines and "clone a graph" needs a hashmap.
The down/up split is the whole game. Pass down when the answer at a node depends on its ancestors (root-to-node path sum, BST min/max bounds, current depth). Return up when the answer depends on the subtree (height, diameter, subtree sum, "does this subtree contain X"). Many hard problems (max path sum, diameter, LCA) do both: return the best downward extension up, while updating a global with the best answer that bends at the node.

Choosing the traversal:

You need…	Use	Why
Fewest steps / shortest path in an unweighted graph or grid	BFS	first time you reach a node is via a shortest path
Level-by-level tree processing	BFS with a level-size loop	one queue drain = one level
Reachability, connected components, path enumeration, subtree aggregate, ordering	DFS (recursion)	natural for "explore fully then back up"
Ordering under dependencies / cycle in a directed graph	Topological sort	linearize a DAG
Dynamic connectivity / grouping / "are A and B connected"	Union-Find	near-O(1) merge & query, no traversal
Shortest path with weights	Dijkstra / Bellman-Ford / 0-1 BFS / Floyd-Warshall	BFS's "one edge = one step" no longer holds

The senior move in an interview is to say this out loud before coding: "This is shortest-path in an unweighted grid, so BFS, O(V+E), and I'll mark visited at enqueue time." That one sentence names the pattern, the complexity, and the classic bug — all at once.

The node types used throughout:

kotlin

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

1. Binary tree traversals — the four skeletons#

Recognition cue. Anything on a binary tree. The question is only which order and what you compute at each node. Pre/in/post-order are DFS variants differing only in when you touch the node relative to recursing into children; level-order is BFS.

Template — recursive DFS. The three orders are one function with the "visit" line moved:

kotlin

fun inorder(node: TreeNode?, out: MutableList<Int>) {
    if (node == null) return
    // preorder:  out.add(node.`val`) here
    inorder(node.left, out)
    out.add(node.`val`)                 // inorder: here
    inorder(node.right, out)
    // postorder: out.add(node.`val`) here
}

java

void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    // preorder:  out.add(node.val) here
    inorder(node.left, out);
    out.add(node.val);                  // inorder: here
    inorder(node.right, out);
    // postorder: out.add(node.val) here
}

Template — iterative in-order (the one interviewers ask you to convert; go left as far as possible, pop-visit, go right):

kotlin

fun inorder(root: TreeNode?): List<Int> {
    val res = ArrayList<Int>()
    val stack = ArrayDeque<TreeNode>()
    var cur = root
    while (cur != null || stack.isNotEmpty()) {
        while (cur != null) { stack.addLast(cur); cur = cur.left }
        cur = stack.removeLast()
        res.add(cur.`val`)
        cur = cur.right
    }
    return res
}

java

List<Integer> inorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        res.add(cur.val);
        cur = cur.right;
    }
    return res;
}

Iterative preorder: push root; loop pop→visit→push right then left. Iterative postorder: run a modified preorder (node, right, left) and prepend each visit to a deque — the reverse is post-order.

Template — level-order BFS (the level-size loop is the crux — snapshot queue.size so one iteration drains exactly one level):

kotlin

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val res = ArrayList<List<Int>>()
    if (root == null) return res
    val q = ArrayDeque<TreeNode>()
    q.addLast(root)
    while (q.isNotEmpty()) {
        val size = q.size                       // freeze this level's width
        val level = ArrayList<Int>(size)
        repeat(size) {
            val node = q.removeFirst()
            level.add(node.`val`)
            node.left?.let { q.addLast(it) }
            node.right?.let { q.addLast(it) }
        }
        res.add(level)
    }
    return res
}

java

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();                    // freeze this level's width
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null)  q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

Complexity (all four): O(n) time; recursion O(h) stack (h = log n balanced, n skewed); BFS O(w) queue where w is the max level width (up to n/2).

Traps. (1) NPE on null children — guard every recurse/enqueue. (2) BFS without the frozen size mixes levels together. (3) A skewed tree makes recursion O(n) deep — on adversarial input that blows the stack (see Problems). (4) Kotlin's `val` needs backticks because val is a keyword.

The down-vs-up frame, concretely#

Pass down (root-to-leaf path sum — the target shrinks as you descend, and each leaf answers locally):

kotlin

fun hasPathSum(root: TreeNode?, target: Int): Boolean {
    if (root == null) return false
    if (root.left == null && root.right == null) return target == root.`val`
    val rem = target - root.`val`
    return hasPathSum(root.left, rem) || hasPathSum(root.right, rem)
}

Return up — max depth, the tiniest aggregate: depth(node) = 1 + max(depth(left), depth(right)).

kotlin

fun maxDepth(root: TreeNode?): Int =
    if (root == null) 0 else 1 + maxOf(maxDepth(root.left), maxDepth(root.right))

java

int maxDepth(TreeNode root) {
    return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Canonical: diameter & max-path-sum — return up, update a global#

The signature move for "hard" tree problems: the recursion returns the best single downward path, but a global captures the best path that bends at the node (uses both children). You cannot return the bent value up — a parent can only extend a straight path.

Diameter (longest path in edges; the bend at a node is leftHeight + rightHeight):

kotlin

private var diameter = 0
fun diameterOfBinaryTree(root: TreeNode?): Int { height(root); return diameter }
private fun height(node: TreeNode?): Int {
    if (node == null) return 0
    val l = height(node.left)
    val r = height(node.right)
    diameter = maxOf(diameter, l + r)      // path bending here, counted in edges
    return 1 + maxOf(l, r)                 // straight path returned to parent
}

java

private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) { height(root); return diameter; }
private int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left), r = height(node.right);
    diameter = Math.max(diameter, l + r);  // path bending here, in edges
    return 1 + Math.max(l, r);             // straight path returned up
}

Max path sum (LC 124 — same shape; clamp negative subtree gains to 0 because you may skip a child):

kotlin

private var best = Int.MIN_VALUE
fun maxPathSum(root: TreeNode?): Int { gain(root); return best }
private fun gain(node: TreeNode?): Int {
    if (node == null) return 0
    val l = maxOf(gain(node.left), 0)      // drop a negative branch
    val r = maxOf(gain(node.right), 0)
    best = maxOf(best, node.`val` + l + r) // bend here
    return node.`val` + maxOf(l, r)        // extend one side upward
}

java

private int best = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) { gain(root); return best; }
private int gain(TreeNode node) {
    if (node == null) return 0;
    int l = Math.max(gain(node.left), 0);  // drop a negative branch
    int r = Math.max(gain(node.right), 0);
    best = Math.max(best, node.val + l + r);// bend here
    return node.val + Math.max(l, r);      // extend one side upward
}

Complexity: O(n) / O(h). Trap: returning the bent value up — wrong, a parent can only inherit a straight extension. Keep the global separate.

Balanced check — fuse two aggregates, short-circuit with a sentinel#

Return the height, or -1 to mean "already unbalanced below," so you check in one post-order pass instead of recomputing heights O(n²):

kotlin

fun isBalanced(root: TreeNode?): Boolean = check(root) >= 0
private fun check(node: TreeNode?): Int {
    if (node == null) return 0
    val l = check(node.left);  if (l < 0) return -1
    val r = check(node.right); if (r < 0) return -1
    return if (Math.abs(l - r) > 1) -1 else 1 + maxOf(l, r)
}

Invert, right-side view, level averages#

Invert (swap children everywhere):

kotlin

fun invertTree(root: TreeNode?): TreeNode? {
    if (root == null) return null
    val tmp = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(tmp)
    return root
}

Right-side view — the last node of each BFS level (swap "last node" for "sum/size" and you have level averages; the skeleton is identical):

kotlin

fun rightSideView(root: TreeNode?): List<Int> {
    val res = ArrayList<Int>()
    if (root == null) return res
    val q = ArrayDeque<TreeNode>()
    q.addLast(root)
    while (q.isNotEmpty()) {
        val size = q.size
        for (i in 0 until size) {
            val node = q.removeFirst()
            if (i == size - 1) res.add(node.`val`)   // rightmost of the level
            node.left?.let { q.addLast(it) }
            node.right?.let { q.addLast(it) }
        }
    }
    return res
}

Lowest common ancestor — with and without parent pointers#

Without parent pointers (the classic post-order: a node is the LCA iff p and q surface from different subtrees):

kotlin

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || root === p || root === q) return root
    val l = lowestCommonAncestor(root.left, p, q)
    val r = lowestCommonAncestor(root.right, p, q)
    return when {
        l != null && r != null -> root      // p and q split here
        l != null -> l
        else -> r
    }
}

java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode l = lowestCommonAncestor(root.left, p, q);
    TreeNode r = lowestCommonAncestor(root.right, p, q);
    if (l != null && r != null) return root; // p and q split here
    return l != null ? l : r;
}

With parent pointers it degenerates to "intersection of two linked lists": collect p's ancestor chain into a set, walk q upward until you hit it. O(h) time, O(h) space.

kotlin

fun lcaWithParents(p: NodeP, q: NodeP): NodeP? {
    val seen = HashSet<NodeP>()
    var a: NodeP? = p; while (a != null) { seen.add(a); a = a.parent }
    var b: NodeP? = q; while (b != null) { if (b in seen) return b; b = b.parent }
    return null
}

Serialize / deserialize — pre-order with explicit null markers#

The # sentinels make the shape unambiguous, so pre-order alone reconstructs the tree (LC 297). The deserializer consumes tokens as a stream — the recursion's structure is the shape:

kotlin

fun serialize(root: TreeNode?): String {
    val sb = StringBuilder()
    fun dfs(node: TreeNode?) {
        if (node == null) { sb.append("#,"); return }
        sb.append(node.`val`).append(',')
        dfs(node.left); dfs(node.right)
    }
    dfs(root)
    return sb.toString()
}
fun deserialize(data: String): TreeNode? {
    val it = data.split(",").iterator()
    fun build(): TreeNode? {
        val t = it.next()
        if (t == "#") return null
        return TreeNode(t.toInt()).apply { left = build(); right = build() }
    }
    return build()
}

java

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    ser(root, sb);
    return sb.toString();
}
private void ser(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append("#,"); return; }
    sb.append(n.val).append(',');
    ser(n.left, sb); ser(n.right, sb);
}
public TreeNode deserialize(String data) {
    Deque<String> t = new ArrayDeque<>(Arrays.asList(data.split(",")));
    return build(t);
}
private TreeNode build(Deque<String> t) {
    String s = t.poll();
    if (s == null || s.equals("#")) return null;
    TreeNode node = new TreeNode(Integer.parseInt(s));
    node.left = build(t);
    node.right = build(t);
    return node;
}

Complexity: O(n) both ways. Trap: the recursion must consume tokens in the same order it wrote them (pre-order out, pre-order in). Reading children in the wrong order silently builds a mirrored/garbage tree.

2. BST-specific patterns#

A binary search tree adds the invariant left subtree < node < right subtree — recursively, not just for immediate children. That invariant is worth O(log h) navigation and a free sorted order via in-order.

Validate a BST — min/max bounds, NOT local checks (the classic trap)#

The #1 BST interview trap: comparing only node against its two children passes on [5, 1, 6, null, null, 3, 7] — the 3 violates the whole-tree rule (it's in 5's right subtree so must be > 5) but is a valid local child of 6. You must thread a (min, max) window down.

kotlin

fun isValidBST(root: TreeNode?): Boolean = valid(root, null, null)
private fun valid(node: TreeNode?, min: Int?, max: Int?): Boolean {
    if (node == null) return true
    if (min != null && node.`val` <= min) return false
    if (max != null && node.`val` >= max) return false
    return valid(node.left, min, node.`val`) && valid(node.right, node.`val`, max)
}

java

public boolean isValidBST(TreeNode root) { return valid(root, null, null); }
private boolean valid(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    if (min != null && node.val <= min) return false;
    if (max != null && node.val >= max) return false;
    return valid(node.left, min, node.val) && valid(node.right, node.val, max);
}

Nullable bounds (Integer/Int? = "unbounded") sidestep the second trap: seeding with Int.MIN_VALUE/MAX_VALUE breaks when a node legitimately holds those values. Long bounds also work.

In-order gives sorted order — kth smallest & the BST iterator#

Because in-order visits a BST ascending, "kth smallest" is "stop the in-order walk at the kth pop." Iterative, so you pay only O(h + k):

kotlin

fun kthSmallest(root: TreeNode?, k: Int): Int {
    val stack = ArrayDeque<TreeNode>()
    var cur = root; var remaining = k
    while (cur != null || stack.isNotEmpty()) {
        while (cur != null) { stack.addLast(cur); cur = cur.left }
        cur = stack.removeLast()
        if (--remaining == 0) return cur.`val`
        cur = cur.right
    }
    return -1
}

The BST iterator (LC 173) is that same paused walk exposed as next()/hasNext() — amortized O(1) per call, O(h) space:

kotlin

class BSTIterator(root: TreeNode?) {
    private val stack = ArrayDeque<TreeNode>()
    init { pushLeft(root) }
    private fun pushLeft(node: TreeNode?) {
        var n = node
        while (n != null) { stack.addLast(n); n = n.left }
    }
    fun hasNext(): Boolean = stack.isNotEmpty()
    fun next(): Int {
        val node = stack.removeLast()
        pushLeft(node.right)
        return node.`val`
    }
}

Insert, delete, and LCA in a BST#

Insert — walk to the null slot, recursing only on the side the ordering dictates (O(h)):

kotlin

fun insertIntoBST(root: TreeNode?, value: Int): TreeNode {
    if (root == null) return TreeNode(value)
    if (value < root.`val`) root.left = insertIntoBST(root.left, value)
    else root.right = insertIntoBST(root.right, value)
    return root
}

Delete (LC 450 — the only fiddly one: a two-child node is replaced by its in-order successor, the smallest value in the right subtree, then that successor is deleted from the right subtree):

kotlin

fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
    if (root == null) return null
    when {
        key < root.`val` -> root.left = deleteNode(root.left, key)
        key > root.`val` -> root.right = deleteNode(root.right, key)
        else -> {
            if (root.left == null) return root.right      // 0 or 1 child
            if (root.right == null) return root.left
            var succ = root.right!!                        // 2 children
            while (succ.left != null) succ = succ.left!!
            root.`val` = succ.`val`
            root.right = deleteNode(root.right, succ.`val`)
        }
    }
    return root
}

LCA in a BST is O(h), not O(n) — the ordering tells you which way to descend; the split point is the LCA. Beating the general-tree LCA is exactly the "did you use the BST property" signal:

kotlin

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
    var node = root
    while (node != null) {
        node = when {
            p.`val` < node.`val` && q.`val` < node.`val` -> node.left
            p.`val` > node.`val` && q.`val` > node.`val` -> node.right
            else -> return node                            // paths diverge → LCA
        }
    }
    return null
}

java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode node = root;
    while (node != null) {
        if (p.val < node.val && q.val < node.val) node = node.left;
        else if (p.val > node.val && q.val > node.val) node = node.right;
        else return node;                                  // paths diverge → LCA
    }
    return null;
}

Sorted array → balanced BST#

Pick the middle as root so both halves are balanced, recurse on the two sides — O(n):

kotlin

fun sortedArrayToBST(nums: IntArray): TreeNode? {
    fun build(lo: Int, hi: Int): TreeNode? {
        if (lo > hi) return null
        val mid = (lo + hi) ushr 1
        return TreeNode(nums[mid]).apply {
            left = build(lo, mid - 1); right = build(mid + 1, hi)
        }
    }
    return build(0, nums.size - 1)
}

3. Graph representations for algorithms#

Internals of the underlying Map/List are in the companion guide; here is just how to build the two shapes you'll actually use. Default to an adjacency list — it's O(V+E) space and iterating a node's neighbors is O(deg), which is what every traversal wants.

kotlin

// Array-of-lists: nodes are 0..n-1. Fastest and most common in interviews.
fun buildAdj(n: Int, edges: Array<IntArray>, directed: Boolean): Array<MutableList<Int>> {
    val adj = Array(n) { mutableListOf<Int>() }
    for ((u, v) in edges) {
        adj[u].add(v)
        if (!directed) adj[v].add(u)          // undirected = add both ways
    }
    return adj
}

java

List<List<Integer>> buildAdj(int n, int[][] edges, boolean directed) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        if (!directed) adj.get(e[1]).add(e[0]); // undirected = add both ways
    }
    return adj;
}

Use a HashMap<T, List<T>> when nodes are labels (strings, coordinates) rather than 0..n-1. Reach for an adjacency matrix boolean[n][n] only when the graph is dense (E ≈ V²) or you need O(1) "is there an edge u→v" tests — it costs O(V²) space regardless of edge count. For weighted graphs store IntArray(v, w) (or a small record) in the list. The single most important distinction to nail before coding: directed vs undirected — it changes edge insertion, cycle detection, and whether Union-Find even applies.

4. DFS on graphs and grids#

Recognition cue. Explore every reachable node / every path; count or label connected regions; detect a cycle; the problem is naturally recursive. On a grid it's "connected regions of cells."

Template — graph DFS with a visited set. The one rule trees don't need: check/mark visited, or cycles loop forever.

kotlin

fun dfs(u: Int, adj: Array<MutableList<Int>>, visited: BooleanArray) {
    visited[u] = true
    for (w in adj[u]) if (!visited[w]) dfs(w, adj, visited)
}

java

void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
    visited[u] = true;
    for (int w : adj.get(u)) if (!visited[w]) dfs(w, adj, visited);
}

Connected components — count the "seed" DFS calls#

Each un-visited node you launch DFS from is one new component:

kotlin

fun countComponents(n: Int, edges: Array<IntArray>): Int {
    val adj = buildAdj(n, edges, directed = false)
    val visited = BooleanArray(n)
    var count = 0
    for (i in 0 until n) if (!visited[i]) { count++; dfs(i, adj, visited) }
    return count
}

Cycle detection — directed vs undirected are DIFFERENT algorithms#

Conflating these is a top-5 graph interview mistake. Directed graphs need 3-color / recursion-stack detection: a back edge to a node currently on the stack (gray) is a cycle. Seeing a finished (black) node is fine — that's just a shared descendant.

kotlin

// 0 = white (unseen), 1 = gray (on current DFS path), 2 = black (finished)
fun hasCycleDirected(n: Int, adj: Array<MutableList<Int>>): Boolean {
    val color = IntArray(n)
    fun dfs(u: Int): Boolean {
        color[u] = 1
        for (w in adj[u]) {
            if (color[w] == 1) return true              // back edge → cycle
            if (color[w] == 0 && dfs(w)) return true
        }
        color[u] = 2
        return false
    }
    for (i in 0 until n) if (color[i] == 0 && dfs(i)) return true
    return false
}

Undirected graphs instead track the parent: any visited neighbor that isn't the node you came from closes a cycle. (A 3-color scheme would false-positive on the trivial u→v→u back-and-forth of a single undirected edge.)

kotlin

fun hasCycleUndirected(n: Int, adj: Array<MutableList<Int>>): Boolean {
    val visited = BooleanArray(n)
    fun dfs(u: Int, parent: Int): Boolean {
        visited[u] = true
        for (w in adj[u]) {
            if (!visited[w]) { if (dfs(w, u)) return true }
            else if (w != parent) return true           // visited non-parent → cycle
        }
        return false
    }
    for (i in 0 until n) if (!visited[i] && dfs(i, -1)) return true
    return false
}

(For undirected connectivity/cycle, Union-Find in §7 is often cleaner.)

Clone graph — DFS + a "original → copy" map#

The map does double duty: memo (don't rebuild a node) and cycle-guard (revisit returns the existing copy):

kotlin

class GNode(var `val`: Int) { val neighbors = ArrayList<GNode?>() }
fun cloneGraph(node: GNode?): GNode? {
    if (node == null) return null
    val map = HashMap<GNode, GNode>()
    fun dfs(cur: GNode): GNode {
        map[cur]?.let { return it }                     // already cloned → stop recursion
        val copy = GNode(cur.`val`)
        map[cur] = copy                                 // register BEFORE recursing (cycles!)
        for (nb in cur.neighbors) copy.neighbors.add(dfs(nb!!))
        return copy
    }
    return dfs(node)
}

Grid-as-graph — the direction-array idiom#

A grid is a graph: cell (r,c) is a node, edges go to its 4 (or 8) neighbors. The reusable idiom is a moves array plus a combined bounds + validity + visited check. Mutating the grid in place ('1'→'0') is a common way to mark visited without extra memory.

Number of islands (LC 200) — DFS sinks each island as you count it:

kotlin

fun numIslands(grid: Array<CharArray>): Int {
    val rows = grid.size; val cols = grid[0].size
    var count = 0
    fun sink(r: Int, c: Int) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return
        grid[r][c] = '0'                                 // mark visited in place
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
    }
    for (r in 0 until rows) for (c in 0 until cols)
        if (grid[r][c] == '1') { count++; sink(r, c) }
    return count
}

java

public int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length, count = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == '1') { count++; sink(grid, r, c); }
    return count;
}
private void sink(char[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';                                       // mark visited in place
    sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}

Flood fill (LC 733) is the same three lines with a color instead of sink — guard start == newColor or you infinite-loop:

kotlin

fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, color: Int): Array<IntArray> {
    val start = image[sr][sc]
    if (start == color) return image
    fun fill(r: Int, c: Int) {
        if (r !in image.indices || c !in image[0].indices || image[r][c] != start) return
        image[r][c] = color
        fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1)
    }
    fill(sr, sc); return image
}

Surrounded regions (LC 130) and Pacific-Atlantic (LC 417) share a key inversion: instead of asking "is this region enclosed / can it reach the ocean," DFS inward from the borders and mark what's reachable; everything unmarked is the answer. Pacific-Atlantic runs the border DFS twice (one ocean each) with an uphill move rule and intersects:

kotlin

fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
    val rows = heights.size; val cols = heights[0].size
    val pac = Array(rows) { BooleanArray(cols) }
    val atl = Array(rows) { BooleanArray(cols) }
    val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
    fun dfs(r: Int, c: Int, seen: Array<BooleanArray>) {
        seen[r][c] = true
        for (d in dirs) {
            val nr = r + d[0]; val nc = c + d[1]
            if (nr in 0 until rows && nc in 0 until cols && !seen[nr][nc] &&
                heights[nr][nc] >= heights[r][c]) dfs(nr, nc, seen)   // flow uphill from sea
        }
    }
    for (r in 0 until rows) { dfs(r, 0, pac); dfs(r, cols - 1, atl) }
    for (c in 0 until cols) { dfs(0, c, pac); dfs(rows - 1, c, atl) }
    val res = ArrayList<List<Int>>()
    for (r in 0 until rows) for (c in 0 until cols)
        if (pac[r][c] && atl[r][c]) res.add(listOf(r, c))
    return res
}

Complexity (all grid DFS): O(R·C) time; O(R·C) worst-case recursion depth (a snake-filled grid) — the space caveat that matters on large grids (see Problems).

5. BFS on graphs and grids — shortest paths in unweighted worlds#

Recognition cue. Fewest steps / minimum moves / shortest path in an unweighted graph or grid; spreading/"minutes until" processes; anything where "one edge = one unit of distance." BFS's guarantee: the first time you dequeue a node, you've reached it by a shortest path — because BFS explores in nondecreasing distance.

Template — grid BFS, distance by levels. The dist == -1 sentinel doubles as the visited set, and setting it at enqueue time is the single most important line (see the trap):

kotlin

fun bfs(start: Int, adj: Array<MutableList<Int>>, n: Int): IntArray {
    val dist = IntArray(n) { -1 }
    val q = ArrayDeque<Int>()
    dist[start] = 0; q.addLast(start)
    while (q.isNotEmpty()) {
        val u = q.removeFirst()
        for (w in adj[u]) if (dist[w] == -1) {          // unvisited
            dist[w] = dist[u] + 1
            q.addLast(w)                                // mark (dist set) AT ENQUEUE
        }
    }
    return dist
}

java

int[] bfs(int start, List<List<Integer>> adj, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    Deque<Integer> q = new ArrayDeque<>();
    dist[start] = 0; q.offer(start);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int w : adj.get(u)) if (dist[w] == -1) {    // unvisited
            dist[w] = dist[u] + 1;
            q.offer(w);                                  // mark (dist set) AT ENQUEUE
        }
    }
    return dist;
}

The visited-at-enqueue rule. Mark a node the instant you add it to the queue, never when you pop it. If you defer marking to dequeue, the same node gets enqueued by every neighbor before it's popped — the queue balloons, work goes exponential, and you TLE. This is the BFS bug interviewers watch for.

How this maps to your world: modeling roaming reachability — "can eMSP A reach CPO B through the hub's peering links, and in how many hops" — is exactly this unweighted multi-hop BFS over a partner-connectivity graph; the "minimum hops" answer falls straight out of the level counter.

Multi-source BFS — seed the queue with ALL sources at once#

Rotting oranges (LC 994): every rotten orange starts at distance 0, so push them all first and BFS in lockstep. One clock, not one-per-source:

kotlin

fun orangesRotting(grid: Array<IntArray>): Int {
    val rows = grid.size; val cols = grid[0].size
    val q = ArrayDeque<IntArray>(); var fresh = 0
    for (r in 0 until rows) for (c in 0 until cols) when (grid[r][c]) {
        2 -> q.addLast(intArrayOf(r, c))                 // all sources seeded
        1 -> fresh++
    }
    if (fresh == 0) return 0
    val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
    var minutes = 0
    while (q.isNotEmpty() && fresh > 0) {
        repeat(q.size) {                                 // one level = one minute
            val (r, c) = q.removeFirst()
            for (d in dirs) {
                val nr = r + d[0]; val nc = c + d[1]
                if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; fresh--; q.addLast(intArrayOf(nr, nc))
                }
            }
        }
        minutes++
    }
    return if (fresh == 0) minutes else -1               // some orange never reached
}

java

public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length, fresh = 0;
    Deque<int[]> q = new ArrayDeque<>();
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) q.offer(new int[]{r, c});   // all sources seeded
            else if (grid[r][c] == 1) fresh++;
        }
    if (fresh == 0) return 0;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    int minutes = 0;
    while (!q.isEmpty() && fresh > 0) {
        int size = q.size();
        for (int i = 0; i < size; i++) {                     // one level = one minute
            int[] cell = q.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; fresh--; q.offer(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

The identical multi-source shape solves 0/1 matrix (LC 542, seed the queue with every 0) and walls-and-gates (LC 286, seed with every gate). No level loop needed if you write distance as dist[nbr] = dist[cur] + 1:

kotlin

fun updateMatrix(mat: Array<IntArray>): Array<IntArray> {
    val rows = mat.size; val cols = mat[0].size
    val dist = Array(rows) { IntArray(cols) { -1 } }
    val q = ArrayDeque<IntArray>()
    for (r in 0 until rows) for (c in 0 until cols)
        if (mat[r][c] == 0) { dist[r][c] = 0; q.addLast(intArrayOf(r, c)) }
    val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
    while (q.isNotEmpty()) {
        val (r, c) = q.removeFirst()
        for (d in dirs) {
            val nr = r + d[0]; val nc = c + d[1]
            if (nr in 0 until rows && nc in 0 until cols && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1; q.addLast(intArrayOf(nr, nc))
            }
        }
    }
    return dist
}

Word ladder — BFS over an implicit graph#

Word ladder (LC 127): nodes are words, edges connect words one letter apart. You don't build the graph — you generate neighbors on the fly by trying all 26 letters at each position. Shortest transformation = BFS:

kotlin

fun ladderLength(begin: String, end: String, wordList: List<String>): Int {
    val dict = wordList.toHashSet()
    if (end !in dict) return 0
    val q = ArrayDeque<String>(); q.addLast(begin)
    val visited = hashSetOf(begin)
    var steps = 1
    while (q.isNotEmpty()) {
        repeat(q.size) {
            val word = q.removeFirst()
            if (word == end) return steps
            val chars = word.toCharArray()
            for (i in chars.indices) {
                val original = chars[i]
                for (ch in 'a'..'z') {
                    chars[i] = ch
                    val next = String(chars)
                    if (next in dict && next !in visited) { visited.add(next); q.addLast(next) }
                }
                chars[i] = original
            }
        }
        steps++
    }
    return 0
}

The same "implicit graph + BFS" idea powers shortest bridge (LC 934 — DFS to paint island A, then multi-source BFS out to island B) and knight minimum moves (an 8-direction move array on an infinite board). Complexity: BFS is O(V+E); word ladder is O(N · L² · 26) for N words of length L (each of the 26·L candidates per word costs O(L) to build and hash).

6. Topological sort — linearize a DAG#

Recognition cue. Order items with prerequisites/dependencies, build/compile order, can you finish all courses, detect a cycle in a directed graph. The output only exists if the graph is a DAG — a cycle means no valid order, which is how topo sort doubles as directed-cycle detection.

Two implementations; know both, lead with Kahn.

Kahn / BFS (indegree) — repeatedly emit a node with no remaining prerequisites. Course Schedule II (LC 210):

kotlin

fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
    val adj = Array(numCourses) { mutableListOf<Int>() }
    val indegree = IntArray(numCourses)
    for ((course, pre) in prerequisites) { adj[pre].add(course); indegree[course]++ }
    val q = ArrayDeque<Int>()
    for (i in 0 until numCourses) if (indegree[i] == 0) q.addLast(i)
    val order = IntArray(numCourses); var idx = 0
    while (q.isNotEmpty()) {
        val u = q.removeFirst()
        order[idx++] = u
        for (w in adj[u]) if (--indegree[w] == 0) q.addLast(w)
    }
    return if (idx == numCourses) order else IntArray(0)   // short order ⇒ cycle
}

java

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indegree[p[0]]++; }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.offer(i);
    int[] order = new int[numCourses];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int w : adj.get(u)) if (--indegree[w] == 0) q.offer(w);
    }
    return idx == numCourses ? order : new int[0];         // short order ⇒ cycle
}

Cycle detection via topo sort: if the emitted order is shorter than V, the un-emitted nodes are locked in a cycle (their indegree never hit 0). This is the cleanest way to answer Course Schedule I (LC 207 — just return idx == numCourses).

DFS post-order — a node is emitted after all its descendants; reverse the finish order. Interleave a 3-color check to reject cycles:

kotlin

fun findOrderDFS(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
    val adj = Array(numCourses) { mutableListOf<Int>() }
    for ((course, pre) in prerequisites) adj[pre].add(course)
    val color = IntArray(numCourses)
    val order = ArrayDeque<Int>(); var cyclic = false
    fun dfs(u: Int) {
        color[u] = 1
        for (w in adj[u]) {
            if (color[w] == 1) { cyclic = true; return }   // back edge ⇒ cycle
            if (color[w] == 0) { dfs(w); if (cyclic) return }
        }
        color[u] = 2
        order.addFirst(u)                                   // prepend = reverse post-order
    }
    for (i in 0 until numCourses) if (color[i] == 0) { dfs(i); if (cyclic) return IntArray(0) }
    return order.toIntArray()
}

Alien dictionary (LC 269) — build the DAG from adjacent word comparisons: the first differing char gives an ordering edge. Watch the prefix trap: ["abc","ab"] is invalid input (a longer word before its own prefix), not an empty edge.

kotlin

fun alienOrder(words: Array<String>): String {
    val adj = HashMap<Char, MutableSet<Char>>()
    val indeg = HashMap<Char, Int>()
    for (w in words) for (c in w) { adj.putIfAbsent(c, mutableSetOf()); indeg.putIfAbsent(c, 0) }
    for (i in 0 until words.size - 1) {
        val a = words[i]; val b = words[i + 1]; val min = minOf(a.length, b.length)
        if (a.length > b.length && a.substring(0, min) == b.substring(0, min)) return ""  // prefix trap
        for (j in 0 until min) if (a[j] != b[j]) {
            if (adj[a[j]]!!.add(b[j])) indeg[b[j]] = indeg[b[j]]!! + 1
            break
        }
    }
    val q = ArrayDeque<Char>()
    for ((c, d) in indeg) if (d == 0) q.addLast(c)
    val sb = StringBuilder()
    while (q.isNotEmpty()) {
        val c = q.removeFirst(); sb.append(c)
        for (next in adj[c]!!) { indeg[next] = indeg[next]!! - 1; if (indeg[next] == 0) q.addLast(next) }
    }
    return if (sb.length == indeg.size) sb.toString() else ""   // leftover ⇒ cycle
}

Minimum height trees (LC 310) is a reverse topo sort on an undirected tree: repeatedly trim degree-1 leaves layer by layer; the 1 or 2 nodes left standing are the centroids. O(V):

kotlin

fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
    if (n == 1) return listOf(0)
    val adj = Array(n) { mutableSetOf<Int>() }
    for ((u, v) in edges) { adj[u].add(v); adj[v].add(u) }
    var leaves = (0 until n).filter { adj[it].size == 1 }.toMutableList()
    var remaining = n
    while (remaining > 2) {
        remaining -= leaves.size
        val next = ArrayList<Int>()
        for (leaf in leaves) {
            val nb = adj[leaf].first()
            adj[nb].remove(leaf)
            if (adj[nb].size == 1) next.add(nb)
        }
        leaves = next
    }
    return leaves
}

Complexity (topo sort): O(V+E) time, O(V) space for both Kahn and DFS.

7. Union-Find (disjoint set) in graph problems#

Recognition cue. Dynamic connectivity — count groups/components, "are A and B connected," detect a cycle in an undirected graph, or merge sets as edges arrive. When connectivity is the whole question and you don't need paths, Union-Find beats a fresh DFS per query. (Structure internals and the α(n) analysis are in the companion guide; here's the algorithmic template and its uses.)

Template — path compression + union by rank, giving near-O(α(n)) ≈ O(1) amortized per op:

kotlin

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n)
    var count = n; private set                       // number of disjoint sets
    fun find(x: Int): Int {                          // find root, compress path
        var root = x
        while (parent[root] != root) root = parent[root]
        var cur = x
        while (parent[cur] != root) { val nxt = parent[cur]; parent[cur] = root; cur = nxt }
        return root
    }
    fun union(a: Int, b: Int): Boolean {             // false if already merged
        val ra = find(a); val rb = find(b)
        if (ra == rb) return false
        when {
            rank[ra] < rank[rb] -> parent[ra] = rb
            rank[ra] > rank[rb] -> parent[rb] = ra
            else -> { parent[rb] = ra; rank[ra]++ }
        }
        count--
        return true
    }
}

java

class UnionFind {
    private final int[] parent, rank;
    private int count;
    UnionFind(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        count = n;
    }
    int count() { return count; }
    int find(int x) {                                // find root, compress path
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) { int nxt = parent[x]; parent[x] = root; x = nxt; }
        return root;
    }
    boolean union(int a, int b) {                    // false if already merged
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        count--;
        return true;
    }
}

Number of provinces / friend circles (LC 547) — union every connected pair, read count:

kotlin

fun findCircleNum(isConnected: Array<IntArray>): Int {
    val n = isConnected.size
    val uf = UnionFind(n)
    for (i in 0 until n) for (j in i + 1 until n) if (isConnected[i][j] == 1) uf.union(i, j)
    return uf.count
}

Redundant connection (LC 684) — the first edge whose two endpoints are already in the same set is the one that closes a cycle. union returning false is the cycle detector:

kotlin

fun findRedundantConnection(edges: Array<IntArray>): IntArray {
    val uf = UnionFind(edges.size + 1)               // nodes are 1..n
    for (e in edges) if (!uf.union(e[0], e[1])) return e
    return intArrayOf()
}

Accounts merge (LC 721) — union accounts that share any email, keyed through an email → owner-id map, then group emails by root:

kotlin

fun accountsMerge(accounts: List<List<String>>): List<List<String>> {
    val uf = UnionFind(accounts.size)
    val emailToId = HashMap<String, Int>()
    for (i in accounts.indices) for (j in 1 until accounts[i].size) {
        val email = accounts[i][j]
        val owner = emailToId[email]
        if (owner != null) uf.union(i, owner) else emailToId[email] = i
    }
    val merged = HashMap<Int, java.util.TreeSet<String>>()
    for ((email, id) in emailToId) merged.getOrPut(uf.find(id)) { java.util.TreeSet() }.add(email)
    return merged.map { (root, emails) -> listOf(accounts[root][0]) + emails }
}

Kruskal's MST (sketch): sort edges by weight ascending; add an edge iff it joins two different components (union returns true); stop at V−1 edges. Union-Find is the cycle filter that makes Kruskal correct:

kotlin

fun kruskalMST(n: Int, edges: Array<IntArray>): Int {   // edge = [u, v, weight]
    edges.sortBy { it[2] }
    val uf = UnionFind(n); var total = 0; var used = 0
    for (e in edges) if (uf.union(e[0], e[1])) {
        total += e[2]
        if (++used == n - 1) break
    }
    return total
}

Complexity: each op ~O(α(n)) amortized (effectively constant); building over E edges is O(E·α(n)), plus O(E log E) if you sort (Kruskal). Trap: Union-Find detects cycles in undirected graphs only — for directed cycles use topo sort or 3-color DFS.

8. Weighted shortest paths#

Once edges carry weights, "one edge = one step" fails and plain BFS is wrong. Pick by the weight profile.

Dijkstra — non-negative weights, greedy with a min-heap#

Recognition cue. Shortest/cheapest/fastest path, all weights ≥ 0. Pop the closest unsettled node, relax its edges, repeat. Use lazy deletion: don't decrease-key; just push the improved (dist, node) and skip stale pops where the popped distance exceeds the recorded best.

Network delay time (LC 743 — shortest path from a source to the farthest node):

kotlin

fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
    val adj = Array(n + 1) { mutableListOf<IntArray>() }      // node → [(nbr, weight)]
    for (t in times) adj[t[0]].add(intArrayOf(t[1], t[2]))
    val dist = IntArray(n + 1) { Int.MAX_VALUE }; dist[k] = 0
    val pq = java.util.PriorityQueue<IntArray>(compareBy { it[0] })  // (dist, node)
    pq.add(intArrayOf(0, k))
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        if (d > dist[u]) continue                            // stale entry — skip
        for (e in adj[u]) {
            val v = e[0]; val w = e[1]
            if (d + w < dist[v]) { dist[v] = d + w; pq.add(intArrayOf(dist[v], v)) }
        }
    }
    var ans = 0
    for (i in 1..n) { if (dist[i] == Int.MAX_VALUE) return -1; ans = maxOf(ans, dist[i]) }
    return ans
}

java

public int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, k});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;                           // stale entry — skip
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) { dist[v] = d + w; pq.offer(new int[]{dist[v], v}); }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        ans = Math.max(ans, dist[i]);
    }
    return ans;
}

Dijkstra generalizes past "sum of weights." Path with minimum effort (LC 1631) relaxes on max(effort_so_far, |Δheight|) instead of a sum — the cost of a path is its worst step, and Dijkstra still works because that cost is monotonic:

kotlin

fun minimumEffortPath(heights: Array<IntArray>): Int {
    val rows = heights.size; val cols = heights[0].size
    val effort = Array(rows) { IntArray(cols) { Int.MAX_VALUE } }; effort[0][0] = 0
    val pq = java.util.PriorityQueue<IntArray>(compareBy { it[0] })  // (effort, r, c)
    pq.add(intArrayOf(0, 0, 0))
    val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
    while (pq.isNotEmpty()) {
        val (e, r, c) = pq.poll()
        if (r == rows - 1 && c == cols - 1) return e
        if (e > effort[r][c]) continue
        for (d in dirs) {
            val nr = r + d[0]; val nc = c + d[1]
            if (nr in 0 until rows && nc in 0 until cols) {
                val ne = maxOf(e, Math.abs(heights[nr][nc] - heights[r][c]))
                if (ne < effort[nr][nc]) { effort[nr][nc] = ne; pq.add(intArrayOf(ne, nr, nc)) }
            }
        }
    }
    return 0
}

The same Dijkstra template with a max relaxation solves swim in rising water (LC 778). Complexity: O(E log V) with a binary heap.

Cheapest flights within K stops — why plain Dijkstra needs care#

Recognition cue. Shortest path with a bound on the number of edges/stops. Plain Dijkstra is greedy on cost and will happily settle a node via a cheap-but-too-many-hops path, then be unable to revisit it within the stop budget — so it can return a wrong answer. The clean fix is Bellman-Ford restricted to k+1 rounds: relax all edges once per round, so after round i you have the cheapest path using ≤ i edges. Copy the distance array each round so a single round can't chain multiple relaxations (LC 787):

kotlin

fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
    var dist = IntArray(n) { Int.MAX_VALUE }; dist[src] = 0
    for (round in 0..k) {                                // k stops = k+1 edges
        val next = dist.copyOf()                         // freeze: ≤ round+1 edges
        for (f in flights) {
            val u = f[0]; val v = f[1]; val w = f[2]
            if (dist[u] != Int.MAX_VALUE && dist[u] + w < next[v]) next[v] = dist[u] + w
        }
        dist = next
    }
    return if (dist[dst] == Int.MAX_VALUE) -1 else dist[dst]
}

java

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {           // k stops = k+1 edges
        int[] next = dist.clone();                       // freeze: ≤ round+1 edges
        for (int[] f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < next[v]) next[v] = dist[u] + w;
        }
        dist = next;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

Trap: relaxing in place (no next copy) lets one round chain several flights, over-counting stops and undercounting price. (You can do it with Dijkstra by carrying stops in the priority-queue state, but the k-round Bellman-Ford is simpler and less error-prone.)

0-1 BFS — weights are only 0 or 1#

Recognition cue. Every edge costs 0 or 1 (e.g., "minimum obstacles to remove," "min flips"). Use a deque: push 0-weight moves to the front, 1-weight to the back. That keeps the deque monotonic in distance — Dijkstra's guarantee at BFS's O(V+E) cost, no heap:

kotlin

fun zeroOneBFS(n: Int, adj: Array<MutableList<IntArray>>, src: Int): IntArray {
    val dist = IntArray(n) { Int.MAX_VALUE }; dist[src] = 0
    val dq = ArrayDeque<Int>(); dq.addFirst(src)
    while (dq.isNotEmpty()) {
        val u = dq.removeFirst()
        for (e in adj[u]) {
            val v = e[0]; val w = e[1]                    // w is 0 or 1
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w
                if (w == 0) dq.addFirst(v) else dq.addLast(v)
            }
        }
    }
    return dist
}

Bellman-Ford — negative edges & negative-cycle detection#

Recognition cue. Some weights are negative (Dijkstra is invalid), or you must detect a negative cycle. Relax all E edges V−1 times; a V-th pass that still relaxes something proves a reachable negative cycle. O(V·E):

kotlin

fun bellmanFord(n: Int, edges: Array<IntArray>, src: Int): IntArray? {
    val dist = IntArray(n) { Int.MAX_VALUE }; dist[src] = 0
    repeat(n - 1) {
        for (e in edges) {
            val u = e[0]; val v = e[1]; val w = e[2]
            if (dist[u] != Int.MAX_VALUE && dist[u] + w < dist[v]) dist[v] = dist[u] + w
        }
    }
    for (e in edges) {                                    // one more pass
        val u = e[0]; val v = e[1]; val w = e[2]
        if (dist[u] != Int.MAX_VALUE && dist[u] + w < dist[v]) return null  // negative cycle
    }
    return dist
}

Floyd-Warshall — all-pairs shortest, tiny dense graphs#

Recognition cue. You need distances between every pair, V is small (≤ ~400), weights may be negative (no negative cycle). Three nested loops with k (the intermediate) outermost. O(V³) time, O(V²) space:

kotlin

fun floydWarshall(n: Int, edges: Array<IntArray>): Array<IntArray> {
    val INF = Int.MAX_VALUE / 2                           // /2 so INF+INF doesn't overflow
    val dist = Array(n) { IntArray(n) { INF } }
    for (i in 0 until n) dist[i][i] = 0
    for (e in edges) dist[e[0]][e[1]] = minOf(dist[e[0]][e[1]], e[2])
    for (k in 0 until n)                                  // intermediate node — MUST be outermost
        for (i in 0 until n)
            for (j in 0 until n)
                if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]
    return dist
}

Trap: the k loop must be the outermost — swap it inward and you compute garbage (paths aren't yet finalized). And guard against INF overflow with MAX_VALUE / 2.

9. The "which graph algorithm" decision tree#

Say this tree out loud in an interview — it is the senior signal. Work top-down from the question, not from an algorithm you happen to remember.

The question is…	Reach for	Time
Shortest path, unweighted graph/grid	BFS	O(V+E)
Spreading from many origins at once	Multi-source BFS	O(V+E)
Shortest path, weights ≥ 0	Dijkstra + min-heap	O(E log V)
Shortest path, weights are 0/1	0-1 BFS + deque	O(V+E)
Shortest path with ≤ k edges/stops	Bellman-Ford, k+1 rounds	O(k·E)
Negative edges / detect negative cycle	Bellman-Ford	O(V·E)
All-pairs, small dense graph	Floyd-Warshall (or Dijkstra ×V)	O(V³)
Ordering under dependencies / DAG cycle	Topological sort (Kahn or DFS)	O(V+E)
Connectivity / grouping, "are A,B connected"	Union-Find (or DFS/BFS)	~O(E·α)
Reachability / path enumeration / subtree work	DFS	O(V+E)
Minimum spanning tree	Kruskal (UF) / Prim (heap)	O(E log E)

Rule of thumb: weights change everything. Unweighted → BFS is optimal and simplest; the moment weights appear, ask "any negative? bounded hops? just 0/1?" and route accordingly.

Problems & how to solve them#

Problem: BFS TLEs or the queue explodes on a big graph. Root cause: marking a node visited at dequeue time instead of enqueue time — every neighbor re-adds the same node before it's popped, so it enters the queue deg(v) times and work goes super-linear. Fix: set the visited flag (or dist) the instant you enqueue, and never enqueue an already-marked node. One node, one enqueue, forever.

Problem: recursion StackOverflowError on a deep tree/graph. Root cause: a skewed tree or a long grid snake gives O(n) recursion depth; the default JVM stack (~512KB–1MB, a few thousand frames) blows on n ≈ 10^4–10^5. Fix: convert to an iterative DFS with an explicit ArrayDeque stack (or BFS), or for a known-shallow case run the recursion on a Thread constructed with a larger stack size. In interviews, say the depth bound out loud and offer the iterative version.

Problem: cycle detection gives wrong answers. Root cause: using the undirected parent-tracking method on a directed graph (or vice-versa). Directed cycles need "back edge to a node still on the recursion stack" (3-color); undirected cycles need "visited neighbor that isn't my parent." Fix: decide directed-vs-undirected first. Directed → 3-color DFS or "topo order shorter than V." Undirected → parent-tracking DFS or Union-Find. They are not interchangeable.

Problem: Dijkstra returns a wrong (too-small) distance. Root cause: running Dijkstra on a graph with negative edges — its greedy "settle the closest node permanently" invariant is false when a later negative edge could have improved an already-settled node. Fix: negative edges ⇒ Bellman-Ford (and it detects negative cycles); non-negative ⇒ Dijkstra. Also remember to skip stale heap entries (if (d > dist[u]) continue), or you re-expand nodes and may relax with an outdated distance.

Problem: grid BFS/DFS visits the same cell repeatedly / counts an island twice. Root cause: forgetting to mark a cell before recursing or before enqueueing, so neighbors bounce back into it. Fix: mark the cell (mutate the grid, or set a visited/dist sentinel) before you push its neighbors. For "count regions," sink the whole region the moment you first touch it.

Problem: "valid BST" passes an invalid tree. Root cause: checking only left < node < right for immediate children — a deep descendant can violate an ancestor's bound while satisfying its parent. Fix: thread a (min, max) window down the recursion; each node must lie strictly inside it, and you tighten the window for each child. Use nullable/Long bounds so Integer.MIN/MAX node values don't false-negative.

Problem: "cheapest flight within k stops" is off by a few stops. Root cause: relaxing edges in place across a round, so one round chains multiple flights and the stop count is undercounted. Fix: Bellman-Ford with a copied distance array per round (relax from the previous round's snapshot), giving exactly "cheapest with ≤ i edges" after round i. Run k+1 rounds.

Interview framing / how to sound senior#

Model the graph explicitly before coding. "Nodes are cells, edges are the 4 orthogonal neighbors, weights are uniform — so this is unweighted shortest path, BFS, O(R·C)." Naming what the nodes and edges are is the Staff+ tell; weak candidates start mutating a grid before saying what it represents. Per the rubric research, senior scoring weights judgment and driving the session over raw speed.
Lead with the decision tree. "Weighted, non-negative → Dijkstra. If it were 0/1 I'd use 0-1 BFS; if negative, Bellman-Ford." Saying the alternatives you rejected and why is worth more than the code.
State the traversal's invariant and complexity in one breath. "BFS, first dequeue is the shortest path, mark visited at enqueue, O(V+E) time, O(V) queue." That sentence pre-empts the classic bug and shows you know why it's correct.
Call the down-vs-up split on tree problems. "I'll return the height up and update a global for the bending path" (diameter/max-path-sum) tells the interviewer you understand the recursion frame, not just a memorized snippet.
Flag version/JVM facts. Kotlin's ArrayDeque (stdlib since 1.4) is your queue and stack; Java uses java.util.ArrayDeque (never Stack — legacy synchronized) and PriorityQueue with a Comparator. Mention the recursion-depth risk on large inputs and the iterative fallback — that's production-readiness thinking, which 2026 infra rubrics reward.
Snowflake-flavored note: infra loops lean on graphs — dependency ordering (Kahn), "simulate a crawler" (BFS), resource/quota reachability — and often on thread-safety around shared structures. If a prompt says "process a stream of dependencies," it's topo sort; narrate that recognition.

Cheat-sheet#

Structure / problem shape	Traversal / algorithm	Time	Space
Tree depth / subtree aggregate	DFS post-order (return up)	O(n)	O(h)
Root-to-leaf constraint	DFS pre-order (carry down)	O(n)	O(h)
Diameter / max path sum	DFS return-up + global for bend	O(n)	O(h)
Level order / right view / averages	BFS + frozen level size	O(n)	O(w)
Validate BST	DFS with (min,max) bounds	O(n)	O(h)
kth smallest / BST iterator	Iterative in-order	O(h+k)	O(h)
LCA in a plain tree	DFS, "split point"	O(n)	O(h)
LCA in a BST	Ordered descent	O(h)	O(1)
Serialize / deserialize	Pre-order + null markers	O(n)	O(n)
Connected components / grouping	DFS/BFS or Union-Find	O(V+E) / O(E·α)	O(V)
Cycle, directed graph	3-color DFS / topo len < V	O(V+E)	O(V)
Cycle, undirected graph	Parent-DFS / Union-Find	O(V+E) / O(E·α)	O(V)
Islands / flood fill / regions	Grid DFS or BFS	O(R·C)	O(R·C)
Shortest path, unweighted	BFS (mark at enqueue)	O(V+E)	O(V)
Spreading from many origins	Multi-source BFS	O(V+E)	O(V)
Ordering with dependencies	Topo sort (Kahn / DFS)	O(V+E)	O(V)
Centroids of a tree	Trim leaves (reverse topo)	O(V)	O(V)
Shortest path, weights ≥ 0	Dijkstra + min-heap	O(E log V)	O(V)
Shortest path, 0/1 weights	0-1 BFS + deque	O(V+E)	O(V)
Shortest path, ≤ k edges	Bellman-Ford, k+1 rounds	O(k·E)	O(V)
Negative edges / neg-cycle	Bellman-Ford	O(V·E)	O(V)
All-pairs shortest	Floyd-Warshall	O(V³)	O(V²)
Minimum spanning tree	Kruskal + Union-Find	O(E log E)	O(V)

Self-test#

Explain the down-vs-up recursion frame and classify these as pass-down, return-up, or both: max depth, root-to-leaf path sum, diameter, validate BST, max path sum.
Why does "valid BST" need (min,max) bounds threaded down rather than local parent-child comparisons? Give the smallest counterexample the local check accepts.
Why must BFS mark a node visited at enqueue time, not dequeue time? What is the concrete failure if you don't?
Directed vs undirected cycle detection: state each algorithm and why they aren't interchangeable.
In Course Schedule, how does the topo-sort output length tell you a cycle exists? Which nodes are the ones left out?
Why is LCA in a BST O(h) but LCA in a general tree O(n)? What property buys the speedup?
Why does Dijkstra break on negative edges? What do you switch to, and what extra thing does it detect?
Why does "cheapest flight within k stops" copy the distance array each Bellman-Ford round? What goes wrong if you relax in place?
When is 0-1 BFS strictly better than Dijkstra, and what data structure replaces the heap?
In Floyd-Warshall, why must the intermediate-node loop k be outermost? Why initialize INF = MAX/2?
Diameter and max-path-sum both "return one thing up but update a global." What exactly is returned vs recorded, and why can't you return the recorded value?
What is the recursion-depth risk of DFS on a skewed tree or a large grid, and what are two production-safe fixes?
When would you choose Union-Find over a DFS to answer connectivity, and what is its per-operation complexity with path compression + union by rank?
Give the full "which graph algorithm" decision tree from a cold problem statement.

Lineage / sources#

BFS/DFS, topological sort, Dijkstra, Bellman-Ford, and Floyd-Warshall are the canonical graph algorithms of CLRS (Introduction to Algorithms); the 3-color / white-gray-black DFS classification and the DAG topo-sort-via-DFS are from there. Kahn's algorithm (1962) is the indegree/BFS topo sort. Union-Find with path compression + union by rank and its inverse-Ackermann α(n) bound are Tarjan's; Kruskal (1956) and Prim/Dijkstra are the classical MST/shortest-path results. 0-1 BFS is folklore from competitive programming. The pattern taxonomy and recognition cues (BFS/DFS, islands, topo sort, Union-Find, heaps) follow Grokking the Coding Interview (DesignGurus/Educative) and NeetCode 150. Problem numbers reference LeetCode (94, 102, 104, 110, 124, 127, 130, 133, 173, 199, 200, 207, 210, 226, 261, 269, 286, 297, 310, 417, 450, 542, 547, 684, 700, 721, 733, 743, 778, 787, 934, 994, 1631). Interview-format and rubric notes (round mix by level, the practical/"simulate a system" tilt at infra shops like Snowflake, the four scoring axes) come from Tech Interview Handbook, interviewing.io's 100K-interview study, and the 2025-26 vendor guides synthesized in the series playbook (00); treat exact round counts and Snowflake specifics as typical-not-guaranteed. For the internals and complexity of every structure used here as a tool — HashMap, ArrayDeque, PriorityQueue, disjoint-set forests — see the companion data-structures-java-kotlin-study-guide.md.