Breadth-first and depth-first traversal for graphs, trees, and grids -- when to use which, with iterative and recursive implementations

BFS & DFS

Breadth-first search (BFS) and depth-first search (DFS) are the two fundamental ways to explore a graph or tree. Almost every graph problem reduces to one of these two traversals with some bookkeeping on top.

BFS vs DFS at a Glance

	BFS	DFS
Data structure	Queue	Stack (or recursion)
Explores	Level by level	As deep as possible first
Best for	Shortest path (unweighted), level-order	Exhaustive search, cycle detection, topological sort
Space	O(width of tree/graph)	O(depth of tree/graph)
Finds shortest path?	Yes (unweighted)	Not guaranteed

Rule of thumb: if the problem mentions "shortest," "minimum steps," or "closest," use BFS. If it mentions "all paths," "connected components," or "can you reach," DFS is often simpler.

BFS Template

function bfs(start: string, graph: Map<string, string[]>): void {
  const queue: string[] = [start];
  const visited = new Set<string>([start]);

  while (queue.length > 0) {
    const node = queue.shift()!;
    // Process node

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

BFS with Level Tracking

Many problems need to know which "level" you are on (distance from start, tree depth, etc.).

function bfsWithLevels(start: string, graph: Map<string, string[]>): number {
  const queue: string[] = [start];
  const visited = new Set<string>([start]);
  let level = 0;

  while (queue.length > 0) {
    const levelSize = queue.length; // snapshot current level size

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      // Process node at this level

      for (const neighbor of graph.get(node) ?? []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    level++;
  }

  return level;
}

The key trick: snapshot queue.length before processing. All nodes dequeued in that batch are at the same level.

DFS Template (Recursive)

function dfs(
  node: string,
  graph: Map<string, string[]>,
  visited: Set<string>
): void {
  visited.add(node);
  // Process node

  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, graph, visited);
    }
  }
}

DFS Template (Iterative with Stack)

Iterative DFS avoids stack overflow on deep graphs and gives you more control.

function dfsIterative(start: string, graph: Map<string, string[]>): void {
  const stack: string[] = [start];
  const visited = new Set<string>();

  while (stack.length > 0) {
    const node = stack.pop()!;

    if (visited.has(node)) continue;
    visited.add(node);
    // Process node

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
}

Note: iterative DFS processes nodes in a different order than recursive DFS (neighbors are visited in reverse). This usually does not matter, but be aware of it.

Grid Traversal

Grids are graphs where each cell connects to its 4 (or 8) neighbors. BFS/DFS on grids is extremely common.

Number of Islands

Count connected components of '1's in a 2D grid.

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== "1") return;

    grid[r][c] = "0"; // mark visited by modifying grid

    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

Time: O(rows * cols), Space: O(rows * cols) worst case for the recursion stack.

Grid BFS Template

function gridBfs(
  grid: number[][],
  startRow: number,
  startCol: number
): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  const queue: [number, number][] = [[startRow, startCol]];
  const visited = new Set<string>();
  visited.add(`${startRow},${startCol}`);
  let steps = 0;

  while (queue.length > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue.shift()!;

      // Check if we reached the goal
      // if (isGoal(r, c)) return steps;

      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        const key = `${nr},${nc}`;

        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          !visited.has(key) &&
          grid[nr][nc] !== 0 // or whatever the wall condition is
        ) {
          visited.add(key);
          queue.push([nr, nc]);
        }
      }
    }

    steps++;
  }

  return -1; // goal not reachable
}

Word Ladder

Transform one word to another, changing one letter at a time, where each intermediate word must be in a dictionary. Find the shortest transformation sequence.

function ladderLength(
  beginWord: string,
  endWord: string,
  wordList: string[]
): number {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const queue: string[] = [beginWord];
  const visited = new Set<string>([beginWord]);
  let steps = 1;

  while (queue.length > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const word = queue.shift()!;

      if (word === endWord) return steps;

      // Try changing each character
      for (let j = 0; j < word.length; j++) {
        for (let c = 97; c <= 122; c++) { // 'a' to 'z'
          const newWord =
            word.slice(0, j) + String.fromCharCode(c) + word.slice(j + 1);

          if (wordSet.has(newWord) && !visited.has(newWord)) {
            visited.add(newWord);
            queue.push(newWord);
          }
        }
      }
    }

    steps++;
  }

  return 0;
}

Time: O(M^2 * N) where M = word length, N = word list size. Space: O(M * N).

Clone Graph

Deep copy a graph given a reference to one node.

interface GraphNode {
  val: number;
  neighbors: GraphNode[];
}

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (!node) return null;

  const cloned = new Map<GraphNode, GraphNode>();

  function dfs(original: GraphNode): GraphNode {
    if (cloned.has(original)) return cloned.get(original)!;

    const copy: GraphNode = { val: original.val, neighbors: [] };
    cloned.set(original, copy);

    for (const neighbor of original.neighbors) {
      copy.neighbors.push(dfs(neighbor));
    }

    return copy;
  }

  return dfs(node);
}

Time: O(V + E), Space: O(V).

Tree Traversal Refresher

Trees are graphs without cycles. No need for a visited set.

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

// DFS variants
function preorder(node: TreeNode | null): number[] {
  if (!node) return [];
  return [node.val, ...preorder(node.left), ...preorder(node.right)];
}

function inorder(node: TreeNode | null): number[] {
  if (!node) return [];
  return [...inorder(node.left), node.val, ...inorder(node.right)];
}

function postorder(node: TreeNode | null): number[] {
  if (!node) return [];
  return [...postorder(node.left), ...postorder(node.right), node.val];
}

// BFS (level-order)
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const level: number[] = [];
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

When to Use BFS vs DFS

Scenario	Use
Shortest path in unweighted graph	BFS
Level-order traversal	BFS
Checking if path exists	Either (DFS is simpler)
Connected components	DFS
Topological sort	DFS (with post-order)
Cycle detection	DFS
Exploring all possibilities	DFS
Grid shortest path	BFS

Complexity Summary

Problem	Time	Space
BFS/DFS on graph	O(V + E)	O(V)
Number of islands	O(R * C)	O(R * C)
Word ladder	O(M^2 * N)	O(M * N)
Clone graph	O(V + E)	O(V)
Tree traversal	O(n)	O(h) for DFS, O(w) for BFS

BFS and DFS are the building blocks. Once you are comfortable with these templates, problems like topological sort, shortest path, and connected components become variations with added bookkeeping.

BFS & DFS

On this page