BFS Pattern — Level Order Traversal and Shortest Path on Unweighted Graphs

BFS earns its place for one reason: on an unweighted graph it finds the shortest path, and DFS does not. Any question containing the words

fewest, minimum steps, nearest or level over an unweighted structure is a BFS

question, and reaching for DFS there is a wrong answer that often still passes the first sample case.

The idea

Expand outward in rings. Visit everything one step away, then everything two steps away, and so on. A queue enforces that order automatically, because nodes come out in the order they went in.

from collections import deque

def bfs(start, neighbours):
    queue = deque([start])
    seen = {start}
    steps = 0

    while queue:
        for _ in range(len(queue)):    # snapshot: exactly one level
            node = queue.popleft()
            if is_goal(node):
                return steps
            for nxt in neighbours(node):
                if nxt not in seen:
                    seen.add(nxt)      # mark on ENQUEUE, not on dequeue
                    queue.append(nxt)
        steps += 1

    return -1

int bfs(Node start) {
    Deque<Node> queue = new ArrayDeque<>();
    Set<Node> seen = new HashSet<>();
    queue.add(start);
    seen.add(start);
    int steps = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();      // snapshot: exactly one level
        for (int i = 0; i < levelSize; i++) {
            Node node = queue.poll();
            if (isGoal(node)) return steps;
            for (Node next : neighbours(node)) {
                if (seen.add(next)) {      // add() returns false if present —
                    queue.add(next);       // marks on ENQUEUE, not dequeue
                }
            }
        }
        steps++;
    }
    return -1;
}

int bfs(Node start) {
    queue<Node> q;
    unordered_set<Node> seen;
    q.push(start);
    seen.insert(start);
    int steps = 0;

    while (!q.empty()) {
        int levelSize = (int)q.size();     // snapshot: exactly one level
        for (int i = 0; i < levelSize; i++) {
            Node node = q.front(); q.pop();
            if (isGoal(node)) return steps;
            for (const Node& next : neighbours(node)) {
                if (seen.insert(next).second) {   // marks on ENQUEUE
                    q.push(next);
                }
            }
        }
        steps++;
    }
    return -1;
}

function bfs(start, neighbours) {
  let queue = [start];
  const seen = new Set([start]);
  let steps = 0;

  while (queue.length) {
    const next = [];                  // build the next level separately —
    for (const node of queue) {       // cheaper than shift() on an array
      if (isGoal(node)) return steps;
      for (const n of neighbours(node)) {
        if (!seen.has(n)) {
          seen.add(n);                // mark on ENQUEUE, not on dequeue
          next.push(n);
        }
      }
    }
    queue = next;
    steps++;
  }
  return -1;
}

Two details carry the whole pattern.

`for _ in range(len(queue))`. Taking the queue's length before the loop snapshots

the current level, so everything enqueued inside the loop belongs to the next one. This is what makes "how many steps" and "give me the nodes level by level" both fall out of the same skeleton.

Mark seen on enqueue. Marking on dequeue lets the same node be queued several times

before it is first processed — still correct, but the queue blows up and on large inputs it times out.

Level order traversal

The tree version is the same loop with the level collected instead of counted:

def level_order(root):
    if not root:
        return []
    out, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        out.append(level)
    return out

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;

    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();     // take the size BEFORE the loop
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        out.add(level);
    }
    return out;   // trees need no visited set — no cycles, one parent each
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> out;
    if (!root) return out;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = (int)q.size();    // take the size BEFORE the loop
        vector<int> level;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        out.push_back(level);
    }
    return out;
}

function levelOrder(root) {
  if (!root) return [];
  const out = [];
  let queue = [root];

  while (queue.length) {
    const level = [], next = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    out.push(level);
    queue = next;
  }
  return out;
}

Trees need no seen set — there are no cycles and each node has one parent. Everything else in the family is a variation on what you take from level: the last value gives

Right Side View, alternating the direction gives Zigzag, the max gives

Largest Value in Each Row.

Multi-source BFS

The variant people miss. When several starting points spread simultaneously, seed the queue with all of them at once rather than running one BFS per source. The rings then expand in parallel and every cell is reached by whichever source is nearest — one O(V + E) pass instead of k of them.

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))     # every rotten orange is a source
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2     # the grid IS the visited set
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1

    return -1 if fresh else minutes

int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length, fresh = 0;
    Deque<int[]> queue = new ArrayDeque<>();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.add(new int[]{r, c});  // ALL sources
            else if (grid[r][c] == 1) fresh++;
        }
    }

    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    int minutes = 0;

    while (!queue.isEmpty() && fresh > 0) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            int[] cell = queue.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;    // the grid IS the visited set
                    fresh--;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh > 0 ? -1 : minutes;
}

int orangesRotting(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size(), fresh = 0;
    queue<pair<int,int>> q;

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) q.push({r, c});   // ALL sources at once
            else if (grid[r][c] == 1) fresh++;
        }

    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    int minutes = 0;

    while (!q.empty() && fresh) {
        int levelSize = (int)q.size();
        for (int i = 0; i < levelSize; i++) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;    // the grid IS the visited set
                    fresh--;
                    q.push({nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh ? -1 : minutes;
}

function orangesRotting(grid) {
  const rows = grid.length, cols = grid[0].length;
  let queue = [], fresh = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);   // ALL sources at once
      else if (grid[r][c] === 1) fresh++;
    }
  }

  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let minutes = 0;

  while (queue.length && fresh) {
    const next = [];
    for (const [r, c] of queue) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;      // the grid IS the visited set
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    queue = next;
    minutes++;
  }
  return fresh ? -1 : minutes;
}

01 Matrix is the same shape: seed the queue with every zero, and the ring number each

cell is reached on is its distance to the nearest zero. Trying to solve it from each 1 instead is the O(n²) trap.

Word Ladder

The one that does not look like a graph. Words are nodes, and two words are neighbours when they differ by one letter — so the shortest transformation sequence is exactly BFS. Do not build the edges by comparing every pair (that is O(n² × L)); generate neighbours on demand by replacing each position with each letter and testing membership in the word set. Bidirectional BFS — expanding from both ends and stopping when the frontiers meet — is the optimisation to mention.

Complexity

O(V + E): every node is enqueued once and every edge is examined once. Space is O(V) for the queue and the visited set — on a wide graph the queue can hold an entire level, which is BFS's real cost against DFS's O(depth) stack.

Mistakes that cost the round

Marking visited on dequeue. Correct but quadratic-ish in practice; it is the usual

cause of a TLE on an otherwise right answer.

Not snapshotting the level length, then wondering why the step count is wrong.
Using DFS for a shortest path on an unweighted graph. DFS finds a path.
Running BFS once per source when a multi-source seed would do it in one pass.
Using BFS on a weighted graph. Once edges have different costs, it is

Dijkstra, not BFS — unless all weights are equal.

What to drill

Binary Tree Level Order Traversal — the snapshot loop.
Rotting Oranges — multi-source, on a grid.
01 Matrix — multi-source distance transform.
Word Ladder — implicit graph, shortest path.

All on the 22 DSA Patterns sheet.

Frequently asked

When should I use BFS instead of DFS?

Use BFS when the question asks for the fewest steps, the shortest path, the nearest thing, or anything level by level on an unweighted graph — BFS reaches every node by a shortest route, DFS does not. Use DFS for connectivity, exhaustive exploration, cycle detection, or when the recursion mirrors the structure, and when a wide graph would make BFS's queue too large.

What is multi-source BFS?

Seeding the queue with every starting point before the loop begins, so all sources expand simultaneously. Each node is then reached by whichever source is closest, in a single O(V + E) pass instead of one BFS per source. Rotting Oranges and 01 Matrix are the standard examples.

Should I mark nodes visited when enqueuing or when dequeuing?

When enqueuing. Marking on dequeue lets the same node sit in the queue many times before it is first processed — still correct, but the queue grows far larger than it needs to, and it is a common cause of time-limit failures on big inputs.

Breadth First Search (BFS)