RoadmapDay 18 / 80
DSAMonth 1 · Week 4

Day 18: Trees: BFS (Breadth-First Search) Traversal

Use a queue to process a tree level by level, and recognize the family of "shortest path" / "level order" problems this unlocks.

Mark this day complete

Study

Concepts

BFS visits nodes in order of distance from the root

BFS uses a Queue (FIFO): start by enqueueing the root, then repeatedly dequeue a node, process it, and enqueue its children. Because a queue preserves insertion order, all nodes at depth d are fully processed before any node at depth d+1 begins — this is precisely what "level order" means.

A common technique is capturing `queue.length` at the start of each while-loop iteration as the current level's node count, so you can process one full level at a time (needed for "return the tree grouped by level" style problems, or "find the level with the maximum sum").

See It

Visualizations

Visualization

BFS visit order on a small binary tree

Numbers show visit order: 1 (root) → 2,3 (level 1) → 4,5,6 (level 2).

1: root (10)
2: left (5)
4: (2)
5: (7)
3: right (15)
6: (20)

Build It

Code Examples

Level-order traversal, grouped by level

js
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const levelSize = queue.length; // snapshot: exactly this many nodes are on this level
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // dequeue
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// [[10], [5, 15], [2, 7, 20]]

queue.shift() is O(n) on a plain array in the worst case — for interviews it is fine, but in production use a proper deque/ring buffer for large queues.

Shortest path in an unweighted binary matrix (grid BFS)

js
function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;

  const queue = [[0, 0, 1]]; // row, col, distance-so-far
  grid[0][0] = 1; // mark visited in place
  const dirs = [-1, 0, 1].flatMap((dr) => [-1, 0, 1].map((dc) => [dr, dc]))
    .filter(([dr, dc]) => dr !== 0 || dc !== 0);

  while (queue.length) {
    const [row, col, dist] = queue.shift();
    if (row === n - 1 && col === n - 1) return dist;

    for (const [dr, dc] of dirs) {
      const r = row + dr, c = col + dc;
      if (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] === 0) {
        grid[r][c] = 1; // mark visited BEFORE enqueueing to avoid duplicates
        queue.push([r, c, dist + 1]);
      }
    }
  }
  return -1;
}

Remember

Key Takeaways

  • BFS = Queue (FIFO). DFS = Stack/recursion (LIFO). The data structure choice IS the algorithm choice.
  • Snapshotting queue.length at the top of the loop is the standard trick for level-by-level processing.
  • BFS on an unweighted graph/grid guarantees the FIRST time you reach a node is via the shortest path — that is why it is the go-to for shortest-path problems.
  • Mark nodes visited at enqueue time, not at dequeue time, to avoid enqueueing the same node multiple times.
  • Trigger words: "level order", "shortest path in an unweighted graph/grid", "minimum number of steps".

Do It

Practice

  1. 1Solve "Binary Tree Right Side View" using level-order BFS, keeping only the last node of each level.
  2. 2Solve "Rotting Oranges" — a multi-source BFS starting from every rotten orange simultaneously.
  3. 3Reimplement levelOrder using a proper index-based pointer instead of queue.shift() and compare performance on a 100k-node tree.