Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes layer by layer, visiting all neighbors at the current depth before moving deeper. It’s the go-to technique for finding shortest paths in unweighted graphs and grids, and it appears constantly in LeetCode Medium problems.

New to BFS? The core idea is simple: use a queue to explore nodes level by level – process all nodes at distance 1, then distance 2, then distance 3, and so on. The first time you reach a node is always the shortest path.

BFS explores a graph level by level A B C D E Level 0 Level 1 Level 2 Queue: [A] Process A → enqueue B, C Queue: [B, C] Process B → enqueue D, E Process C → E already visited Queue: [D, E] Process D, E → no new neighbors Queue: [] → Done! Level 0 (start) Level 1 Level 2

Summary: When to Use Each BFS Pattern

| Pattern | When to Use | Time | Space | |—|—|—|—| | Basic BFS | Shortest path (unweighted), level-order | O(V+E) | O(V) | | Grid BFS | Grid shortest path, nearest cell | O(M × N) | O(M × N) | | Multi-source | Distance from ANY source | O(M × N) | O(M × N) | | Level-order | Tree level processing | O(N) | O(N) | | BFS + State | Multiple dimensions (keys, masks) | O(text{States}) | O(text{States}) |

Contents

Basic BFS

When to use: The problem says “shortest path” or “minimum steps” in an unweighted graph, or asks you to explore all reachable nodes. Look for phrases like “fewest moves,” “minimum number of operations,” or “can you reach.”

Breadth-First Search explores nodes level by level using a queue.

ID Title Link Solution
841 Keys and Rooms Link Solution 
// import java.util.*;
// BFS on graph (adjacency list)
static void bfs(int[][] graph, int start) {
    Queue<Integer> q = new LinkedList<>();
    boolean[]visited(graph.size(), false);

    q.offer(start);
    visited[start] = true;

    while (!q.isEmpty()) {
        int node = q.get(0);
        q.poll();

        // Process node
        cout << node << " ";

        // Explore neighbors
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.offer(neighbor);
            }
        }
    }
}
ID Title Link Solution
841 Keys and Rooms Link Solution

BFS on Grid

When to use: The problem gives you a 2D matrix/grid and asks for shortest distance between cells, number of connected components (islands), or nearest cell of a certain type. Look for “grid,” “matrix,” “4-directional,” or “adjacent cells.”

BFS for 2D grid problems (4-directional or 8-directional).

BFS expands outward on a grid 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 5 2 3 # 5 6 3 4 5 6 7 4 5 6 7 8 BFS wavefront expands one step at a time from start Wall at (2,2) forces BFS to go around it Distance from start 0 (start) 1–2 3–4 5–6 7–8 Wall
ID Title Link Solution
200 Number of Islands Link Solution
695 Max Area of Island Link Solution 
// import java.util.*;
// BFS on 2D grid (4-directional)
static int bfsGrid(char[][]& grid, int[] start, int[] target) {
    int m = grid.length, n = grid[0].length;
    queue<int[]> q;
    int[][] dist(m, int[](n, -1));
    List<int[]> dirs = {{0,1\}, \{0,-1\}, \{1,0\}, \{-1,0}}
    q.offer(start);
    dist[start[0]][start[1]] = 0;

    while (!q.isEmpty()) {
        auto [x, y] = q.get(0);
        q.poll();

        if (new int[] {x, y} == target) {
            return dist[x][y];
        }

        for (var e : dirs.entrySet()) {
            int nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.offer(new int[] {nx, ny});
            }
        }
    }

    return -1;
}

// Count connected components (Number of Islands)
static int numIslands(char[][]& grid) {
    int m = grid.length, n = grid[0].length;
    int count = 0;
    List<int[]> dirs = {{0,1\}, \{0,-1\}, \{1,0\}, \{-1,0}}
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                count++;
                queue<int[]> q;
                q.offer(new int[] {i, j});
                grid[i][j] = '0';

                while (!q.isEmpty()) {
                    auto [x, y] = q.get(0);
                    q.poll();

                    for (var e : dirs.entrySet()) {
                        int nx = x + dx, ny = y + dy;
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                            grid[nx][ny] == '1') {
                            grid[nx][ny] = '0';
                            q.offer(new int[] {nx, ny});
                        }
                    }
                }
            }
        }
    }

    return count;
}
ID Title Link Solution
200 Number of Islands Link Solution
695 Max Area of Island Link Solution

Multi-source BFS

When to use: The problem asks for the distance from ANY source (not one specific source). Classic signals: “distance to nearest 0,” “rotting spreads from all rotten oranges simultaneously,” or “fill from all gates at once.”

Start BFS from multiple sources simultaneously – enqueue all starting points before the loop begins.

Multi-source BFS — distance to nearest source 0 1 2 3 4 0 src 1 2 1 0 src 1 2 3 2 1 2 3 2 3 2 3 2 1 2 3 2 1 0 src 1 2 All sources enqueued at distance 0 BFS expands from every source simultaneously. Each cell shows distance to the nearest source. Legend Source (dist 0) Dist 1 Dist 2 Dist 3
ID Title Link Solution
286 Walls and Gates Link Solution
542 01 Matrix Link -
317 Shortest Distance from All Buildings Link Solution
994 Rotting Oranges Link Solution 
// import java.util.*;
// Multi-source BFS (e.g., 01 Matrix)
int[][] updateMatrix(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    queue<int[]> q;
    int[][] dist(m, int[](n, -1));
    List<int[]> dirs = {{0,1\}, \{0,-1\}, \{1,0\}, \{-1,0}}
    // Add all zeros as starting points
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (mat[i][j] == 0) {
                q.offer(new int[] {i, j});
                dist[i][j] = 0;
            }
        }
    }

    while (!q.isEmpty()) {
        auto [x, y] = q.get(0);
        q.poll();

        for (var e : dirs.entrySet()) {
            int nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.offer(new int[] {nx, ny});
            }
        }
    }

    return dist;
}
ID Title Link Solution
286 Walls and Gates Link Solution
542 01 Matrix Link -
317 Shortest Distance from All Buildings Link Solution
994 Rotting Oranges Link Solution

BFS for Shortest Path

When to use: You need the shortest path and all edges have equal weight (or cost = 1 per step). Look for “minimum number of steps,” “shortest transformation sequence,” or “fewest moves to reach target.”

BFS finds shortest path in unweighted graphs – the first time you reach a node is guaranteed to be via the shortest path.

ID Title Link Solution
1091 Shortest Path in Binary Matrix Link Solution
127 Word Ladder Link -
433 Minimum Genetic Mutation Link Solution
1197 Minimum Knight Moves Link Solution 
// import java.util.*;
// Shortest path in unweighted graph
static int shortestPath(int[][] graph, int start, int target) {
    Queue<Integer> q = new LinkedList<>();
    int[]dist(graph.size(), -1);

    q.offer(start);
    dist[start] = 0;

    while (!q.isEmpty()) {
        int node = q.get(0);
        q.poll();

        if (node == target) {
            return dist[node];
        }

        for (int neighbor : graph[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.offer(neighbor);
            }
        }
    }

    return -1;
}
ID Title Link Solution
1091 Shortest Path in Binary Matrix Link Solution
127 Word Ladder Link -
433 Minimum Genetic Mutation Link Solution
1197 Minimum Knight Moves Link Solution

Level-order Traversal

When to use: The problem asks you to process a tree level by level. Look for “level order,” “zigzag order,” “vertical order,” “right side view,” or “cousins in a binary tree.”

BFS for tree level-order traversal – use q.size() to process one complete level per iteration.

ID Title Link Solution
102 Binary Tree Level Order Traversal Link Solution
103 Binary Tree Zigzag Level Order Traversal Link Solution
314 Binary Tree Vertical Order Traversal Link Solution
429 N-ary Tree Level Order Traversal Link Solution
993 Cousins in Binary Tree Link Solution
863 All Nodes Distance K in Binary Tree Link Solution 
// import java.util.*;
// Binary Tree Level Order Traversal
int[][] levelOrder(TreeNode root) {
    List<int[]> result = new ArrayList<>();
    if (!root) return result;

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; ++i) {
            TreeNode node = q.get(0);
            q.poll();
            level.add(node.val);

            if (node.left) q.offer(node.left);
            if (node.right) q.offer(node.right);
        }

        result.add(level);
    }

    return result;
}

// Zigzag Level Order Traversal
int[][] zigzagLevelOrder(TreeNode root) {
    List<int[]> result = new ArrayList<>();
    if (!root) return result;

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    boolean leftToRight = true;

    while (!q.isEmpty()) {
        int size = q.size();
        int[] level = new int[size];

        for (int i = 0; i < size; ++i) {
            TreeNode node = q.get(0);
            q.poll();

            int index = leftToRight ? i : size - 1 - i;
            level[index] = node.val;

            if (node.left) q.offer(node.left);
            if (node.right) q.offer(node.right);
        }

        result.add(level);
        leftToRight = !leftToRight;
    }

    return result;
}
ID Title Link Solution
102 Binary Tree Level Order Traversal Link Solution
103 Binary Tree Zigzag Level Order Traversal Link Solution
314 Binary Tree Vertical Order Traversal Link Solution
429 N-ary Tree Level Order Traversal Link Solution
993 Cousins in Binary Tree Link Solution
863 All Nodes Distance K in Binary Tree Link Solution

BFS with State

When to use: The shortest path depends on more than just position – you also need to track keys collected, obstacles eliminated, a bitmask of visited nodes, or other extra dimensions. Look for “at most k obstacles,” “collect all keys,” or “visit all nodes.”

BFS when state includes more than just position – expand the visited array to cover all state dimensions.

BFS with state = (position, keys_collected) Grid with keys & doors S · A a · · · b B key (collect) door (need key) State = (row, col, keys_bitmask) Bitmask tracks collected keys: a b = 00 (no keys) ❶ Start: (0, 0) 0 0 no keys ↓ pick up key a ❷ Got key a: (1, 0) 1 0 has a → can open A ↓ pick up key b ❸ Got both: (2, 1) 1 1 has a,b → can open B Same cell can be visited with different key sets → different states!
ID Title Link Solution
1293 Shortest Path in a Grid with Obstacles Elimination Link -
847 Shortest Path Visiting All Nodes Link - 
static int shortestPath(int[][] grid, int k) {
    int m = grid.length, n = grid[0].length;
    boolean[][][] visited = new boolean[m][n][k + 1];
    Queue<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{0, 0, 0, 0});
    visited[0][0][0] = true;
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    while (!q.isEmpty()) {
        int[] state = q.poll();
        int x = state[0], y = state[1], obstacles = state[2], steps = state[3];

        if (x == m - 1 && y == n - 1) {
            return steps;
        }

        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                int newObstacles = obstacles + grid[nx][ny];
                if (newObstacles <= k && !visited[nx][ny][newObstacles]) {
                    visited[nx][ny][newObstacles] = true;
                    q.offer(new int[]{nx, ny, newObstacles, steps + 1});
                }
            }
        }
    }

    return -1;
}
ID Title Link Solution
1293 Shortest Path in a Grid with Obstacles Elimination Link -
847 Shortest Path Visiting All Nodes Link -

More templates