Graph Traversal Pattern

Why this pattern matters for LeetCode

Trees are a special case of graphs — acyclic, rooted, and connected. Real graph problems add two complications: cycles (your traversal can loop forever without a visited set) and disconnected components (a single traversal from one node won't reach everything). These two additions — a visited set and an outer loop over all nodes — transform tree traversal into graph traversal. Most grid problems (islands, mazes, flood fill) are disguised graph problems where cells are nodes and adjacent cells are edges.

What the Graph Traversal pattern is

Graph traversal visits every node exactly once. DFS goes as deep as possible before backtracking — use it for connectivity checks, path existence, and cycle detection. BFS visits all nodes at the current distance before going deeper — use it for shortest path and minimum steps in unweighted graphs. Both require a visited set to prevent revisiting nodes in a cycle. For disconnected graphs, wrap the traversal in an outer loop over all nodes and start a new traversal whenever you find an unvisited one.

Reach for Graph Traversal when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Graph Traversal

• ✓Counting connected components, islands, or regions (Number of Islands)
• ✓Detecting cycles in a directed graph (Course Schedule — if a cycle exists, the schedule is impossible)
• ✓Finding the shortest path in an unweighted graph — BFS, where each level is one step
• ✓Determining whether a path exists between two nodes
• ✓Flood-fill style grid problems — spread from a starting cell to all reachable neighbors

When NOT to use Graph Traversal

• ✕The input is a tree — Tree Traversal is simpler and doesn't need a visited set or outer loop
• ✕You need shortest path in a weighted graph — Dijkstra's algorithm handles that
• ✕The graph has a special structure (DAG, bipartite) that a more targeted algorithm exploits directly
• ✕The problem reduces to a linear scan rather than actual node-by-node traversal

Better alternative: In those cases, Tree Traversal (for acyclic rooted trees), Dijkstra's (for weighted shortest path), or Topological Sort (for DAG ordering) is more appropriate.

JavaScript code template

Number of Islands — O(m × n) time, O(m × n) space

function numIslands(grid) {
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= grid.length) return;
    if (c < 0 || c >= grid[0].length) return;
    if (grid[r][c] !== "1") return; // water or already visited

    grid[r][c] = "0"; // mark visited by sinking the cell in-place
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === "1") {
        count++;   // new unvisited island — start a traversal
        dfs(r, c); // sink all connected land cells
      }
    }
  }

  return count;
}

The outer loop is the key — it handles disconnected components by starting a new DFS from every unvisited land cell. When an unvisited '1' is found, increment the count and DFS to sink all connected land by marking cells '0'. Sinking avoids allocating a separate visited array by mutating the grid directly. Each cell is visited at most once — sunk cells return immediately on the grid[r][c] !== '1' check.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Decide: DFS (connectivity, path existence, cycle detection) or BFS (shortest path, minimum steps)?
2. 2Create a visited set — or mark cells in-place if mutating the input is allowed.
3. 3Write the traversal: check bounds and whether the node is valid and unvisited, mark it visited, then recurse or enqueue in all valid directions.
4. 4If the graph may be disconnected, wrap the traversal in an outer loop over all nodes. Start a new traversal from each unvisited node.
5. 5Accumulate your answer in the outer loop (count of components started) or inside the traversal (shortest distance reached).

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Flood Fill

  DFS from a starting pixel, painting every connected same-color cell — the grid-as-graph pattern in its simplest form.

  Premium→
• Number of Islands

  Outer loop over the grid; DFS to sink each connected land region. Count how many times you start a DFS.

  Premium→
• Max Area of Island

  DFS returns the size of the island it visits. Track the maximum return value across all islands.

  Premium→

Coming soon

• Clone Graph

  DFS through the original graph; use a Map from original node to clone to track visited nodes and avoid re-cloning.

  Coming soon
• Course Schedule

  Detect a cycle in a directed graph — if a cycle exists, some course depends on itself and the schedule is impossible.

  Coming soon

Common mistakes beginners make

• ✕Forgetting the visited set — without it, DFS revisits nodes in a cycle and runs forever.
• ✕Marking a node as visited after recursing into it instead of before — other paths to the same node will re-enter it before it's marked, causing duplicate work or infinite loops.
• ✕Forgetting the outer loop — if the graph is disconnected, a single traversal from one node won't reach all components. Always check every node.
• ✕Treating a graph like a tree — trees are acyclic and rooted so no visited set is needed and one traversal covers everything. Graphs need both additions.

DFS vs BFS

Choose the right tool for the job.

Time and space complexity

You visit each node once (V) and traverse each edge once in each direction (E). The visited set and the recursion stack (DFS) or queue (BFS) each hold at most V nodes. For m × n grids, V = m × n and E ≤ 4V since each cell has at most four neighbors — giving O(m × n) time and space.

Frequently asked questions

How is Graph Traversal different from Tree Traversal?

Trees are acyclic and have a single root — no visited set is needed because you can never revisit a node, and one traversal from the root covers everything. Graphs can have cycles (need a visited set to prevent infinite loops) and may be disconnected (need an outer loop to start from every unvisited node). Tree traversal is a special case of graph traversal with those two constraints removed.

When should I use DFS vs BFS?

DFS for connectivity, path existence, and cycle detection — the call stack naturally tracks your current path, which is useful for backtracking and detecting when you revisit a node in the current path. BFS for shortest path and minimum steps in unweighted graphs — the queue processes nodes in order of their distance from the start, so the first time you reach the target is provably the shortest path.

How do I handle a disconnected graph?

Wrap your traversal in a loop over all nodes. If a node hasn't been visited, start a new traversal from it — this discovers one connected component. The number of times you start a new traversal is the number of components. Without this outer loop, you only explore the component containing your starting node.

Can I use grid mutation instead of a separate visited set?

Yes, when the problem allows modifying the input. Marking '1' as '0' in Number of Islands avoids allocating a separate boolean grid. If the problem says don't modify the input, use a Set of visited coordinates (as 'r,c' strings) or a boolean matrix of the same dimensions as the grid.