BFS Pattern with Queues: Level-Order and Shortest Path

Breadth-First Search (BFS) explores nodes level by level. A queue is the natural data structure because it processes nodes in the order they were discovered — First In, First Out.

The BFS Template

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = {start}

    while queue:
        node = queue.popleft()
        process(node)

        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Level-Order Tree Traversal

Process all nodes at depth d before any node at depth d+1:

def level_order(root):
    """
    Return list of lists, one per level.
    Time: O(n), Space: O(n)
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

Trace

Tree:       1
          /   \
         2     3
        / \     \
       4   5     6

Queue states:
Start:   [1]           → level 0: [1]
After:   [2, 3]        → level 1: [2, 3]
After:   [4, 5, 6]     → level 2: [4, 5, 6]

Result: [[1], [2, 3], [4, 5, 6]]

Shortest Path in Unweighted Graph

BFS guarantees the shortest path (fewest edges) in an unweighted graph:

def shortest_path(graph, start, end):
    """
    Find shortest path in unweighted graph.
    Time: O(V + E), Space: O(V)
    """
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()

        if node == end:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path exists

BFS on a Grid

Many interview problems use BFS on a 2D grid:

def bfs_grid(grid, start_r, start_c):
    """BFS on a 2D grid."""
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start_r, start_c, 0)])  # row, col, distance
    visited = {(start_r, start_c)}
    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                and (nr, nc) not in visited
                and grid[nr][nc] != '#'):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

Why Queue and Not Stack?

BFS with a queue guarantees that when you first reach a node, you’ve found the shortest path to it. DFS with a stack might find a longer path first.

Edge Cases

• Empty graph/tree — return empty result
• Single node — return immediately
• Disconnected graph — BFS only visits the connected component
• Cycles — the visited set prevents infinite loops

When to Use BFS

• Shortest path in unweighted graph
• Level-order traversal
• Finding all nodes within k distance
• Topological sort (Kahn’s algorithm)
• Multi-source BFS (rotten oranges, walls and gates)

Related Problems

• Binary Tree Level Order (LeetCode 102)
• Shortest Path in Binary Matrix (LeetCode 1091)
• Rotten Oranges (LeetCode 994)
• Word Ladder (LeetCode 127)