Breadth-First for Distance

Tree and graph questions sort into two families: is this reachable / collect everything — depth-first — and what is the fewest steps / what belongs to this row — breadth-first. The sorting is not taste. BFS explores strictly in order of distance: it finishes every node at distance d before it touches any node at distance d + 1. That single property is why the first time BFS reaches a node is necessarily along a shortest path — and why DFS, which dives, cannot promise it.

The frontier is the whole algorithm

BFS in its honest shape: a frontier of nodes at the current distance, and the loop that builds the next frontier from it.

export function hopsBetween(edges: Array<[string, string]>, from: string, to: string): number {
  if (from === to) return 0

  const adjacency = new Map<string, string[]>()
  for (const [a, b] of edges) {
    // undirected: register both directions
  }

  const visited = new Set<string>([from])
  let frontier: string[] = [from]
  let distance = 0

  while (frontier.length > 0) {
    distance += 1
    const next: string[] = []
    for (const node of frontier) {
      for (const neighbor of adjacency.get(node) ?? []) {
        if (visited.has(neighbor)) continue
        if (neighbor === to) return distance
        visited.add(neighbor)
        next.push(neighbor)
      }
    }
    frontier = next
  }
  return -1
}

The load-bearing line is visited.add(neighbor) at enqueue time, not at dequeue time. Marking late lets the same node enter the next frontier from two different parents — wasted work in a tree, and in a graph with cycles it is the difference between terminating and not. A node reached from two sides in the same round is visited once; the second path to it is simply never queued.

for (const neighbor of adjacency.get(node) ?? []) {
  if (visited.has(neighbor)) continue
  if (neighbor === to) return distance
  visited.(neighbor)
  next.push(neighbor)
}

Levels out of the same loop

Level-order on a tree is BFS with the loop's bookkeeping exposed: the frontier's size at the top of a round is exactly one row.

export function levelOrder(root: TreeNode | undefined): number[][] {
  if (root === undefined) return []

  const levels: number[][] = []
  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const row: number[] = []
    const rowSize = queue.length

    for (let i = 0; i < rowSize; i++) {
      const node = queue.shift() as TreeNode
      row.push(node.value)
      if (node.left !== undefined) queue.push(node.left)
      if (node.right !== undefined) queue.push(node.right)
    }
    levels.push(row)
  }
  return levels
}

The snapshot — rowSize taken before the row drains — is what separates rows. Children arriving during the round join the next frontier; a loop that drains while (queue.length) instead flattens every level into one. Same loop, one captured number, different output: this is the cheapest interview trick with the highest hit rate.

while (queue.length > 0) {
  const row: number[] = []
  const rowSize = queue.

  for (let i = 0; i < rowSize; i++) {
    const node = queue.shift() as TreeNode
    row.push(node.value)
  }
  levels.push(row)
}

A grid is a graph with four edges

Counting islands needs no adjacency map. Each land cell is a node, its up/down/left/right neighbors are its edges, and "visited" can be written directly onto the grid by sinking land to water as you walk it. One DFS or BFS per island, started only where land remains, and the count of walks started is the island count. The insight to carry: the grid does not need to be converted to be searched — the neighbor arithmetic row ± 1, col ± 1 is the edge list.

How to debug a traversal

Print the frontier, per round, with the distance. For BFS the frontier should read like a stone in a pond — everything at one hop, then two hops; a frontier that mixes distances means a node was marked late. Count visited.size against the node total: stuck below it while the loop ended means you marked on dequeue and double-queued; above it means the grid or the visited set leaks between walks. For grid walks, print the grid after each island — land that survives a sweep is a walk that never reached it, almost always a neighbor direction dropped from the four.

Where this bites

• Marking visited on dequeue. Cycles queue forever, big graphs queue twice. Counter: the mark and the push are one unit — a node enters the visited set the moment it enters the frontier.
• BFS for existence, DFS for distance. Swapped, both still terminate and both are wrong: BFS wastes memory cataloguing by distance when a yes/no needed one dive, and DFS returns a path and calls it shortest. Counter: the question's noun decides — "reachability" dives, "fewest" expands.
• Draining the queue without the row snapshot. Level outputs collapse into one flat list, and distance bookkeeping loses its unit. Counter: capture the frontier's size the instant the round begins; it is the only moment the count is honest.
• A shared visited set between islands. Each island walk must see untouched land, so a set shared across walks (or not reset) undercounts islands. Counter: sinking visited cells into water makes the grid its own visited set, immune to reset bugs.