Breadth-First Search (BFS) Pattern

Overview

Explore nodes level by level using a queue. Ideal for finding shortest paths in unweighted graphs and exploring neighbors before going deeper.

When to Use

• Shortest path in unweighted graph
• Level-order traversal
• Finding minimum steps/moves
• All nodes at distance K
• Connected components
• Bipartite graph checking
• Word ladder / transformation problems

Key Insight: BFS uses a queue to visit nodes level by level, ensuring shortest paths in unweighted graphs.

Template Code

Basic BFS on Graph

public void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();

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

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("Visited: " + node);

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Binary Tree Level Order Traversal

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

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

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        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.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
    }

    return result;
}

Shortest Path in Unweighted Graph

public int shortestPath(int start, int end, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<int[]> queue = new LinkedList<>();  // [node, distance]

    queue.offer(new int[]{start, 0});
    visited[start] = true;

    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int node = current[0], dist = current[1];

        if (node == end) {
            return dist;
        }

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(new int[]{neighbor, dist + 1});
            }
        }
    }

    return -1;  // No path found
}

Number of Islands (Grid BFS)

public int numIslands(char[][] grid) {
    int count = 0;
    int m = grid.length, n = grid[0].length;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                bfsIsland(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

private void bfsIsland(char[][] grid, int row, int col) {
    int m = grid.length, n = grid[0].length;
    int[][] directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    Queue<int[]> queue = new LinkedList<>();

    queue.offer(new int[]{row, col});
    grid[row][col] = '0';

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();

        for (int[] dir : directions) {
            int newRow = cell[0] + dir[0];
            int newCol = cell[1] + dir[1];

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
                && grid[newRow][newCol] == '1') {
                grid[newRow][newCol] = '0';
                queue.offer(new int[]{newRow, newCol});
            }
        }
    }
}

Rotting Oranges (Multi-source BFS)

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    // Add all rotten oranges to queue
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
            } else if (grid[i][j] == 1) {
                fresh++;
            }
        }
    }

    if (fresh == 0) return 0;

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

    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();
        minutes++;

        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();

            for (int[] dir : directions) {
                int r = cell[0] + dir[0];
                int c = cell[1] + dir[1];

                if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
                    grid[r][c] = 2;
                    fresh--;
                    queue.offer(new int[]{r, c});
                }
            }
        }
    }

    return fresh == 0 ? minutes : -1;
}

Word Ladder (Shortest Transformation)

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;

    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    queue.offer(beginWord);
    visited.add(beginWord);
    int level = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            String word = queue.poll();

            if (word.equals(endWord)) {
                return level;
            }

            // Try all single-character transformations
            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];

                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;

                    chars[j] = c;
                    String newWord = new String(chars);

                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        queue.offer(newWord);
                        visited.add(newWord);
                    }
                }

                chars[j] = original;
            }
        }

        level++;
    }

    return 0;
}

Binary Tree Zigzag Level Order

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

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

    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();

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

            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val);
            }

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

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

    return result;
}

All Nodes Distance K in Binary Tree

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    // Build parent map
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    buildParentMap(root, null, parentMap);

    // BFS from target
    Queue<TreeNode> queue = new LinkedList<>();
    Set<TreeNode> visited = new HashSet<>();

    queue.offer(target);
    visited.add(target);
    int distance = 0;

    while (!queue.isEmpty()) {
        if (distance == k) {
            List<Integer> result = new ArrayList<>();
            for (TreeNode node : queue) {
                result.add(node.val);
            }
            return result;
        }

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

            // Check left, right, and parent
            if (node.left != null && !visited.contains(node.left)) {
                visited.add(node.left);
                queue.offer(node.left);
            }
            if (node.right != null && !visited.contains(node.right)) {
                visited.add(node.right);
                queue.offer(node.right);
            }
            TreeNode parent = parentMap.get(node);
            if (parent != null && !visited.contains(parent)) {
                visited.add(parent);
                queue.offer(parent);
            }
        }

        distance++;
    }

    return new ArrayList<>();
}

private void buildParentMap(TreeNode node, TreeNode parent,
                            Map<TreeNode, TreeNode> map) {
    if (node == null) return;
    map.put(node, parent);
    buildParentMap(node.left, node, map);
    buildParentMap(node.right, node, map);
}

Time & Space Complexity

Problem	Time	Space
Graph BFS	O(V + E)	O(V)
Level order	O(n)	O(n)
Grid BFS	O(m × n)	O(m × n)
Word ladder	O(n × m × 26)	O(n × m)
Islands	O(m × n)	O(min(m, n))

Common Interview Questions

1. Binary Tree Level Order Traversal - Basic level order
2. Binary Tree Zigzag Level Order - Alternating direction
3. Binary Tree Right Side View - Rightmost at each level
4. Average of Levels - Mean value per level
5. Number of Islands - Count connected components
6. Rotting Oranges - Multi-source BFS
7. 01 Matrix - Distance to nearest 0
8. Word Ladder - Shortest transformation sequence
9. Shortest Path in Binary Matrix - Grid navigation
10. Open the Lock - State space BFS
11. Minimum Knight Moves - Chess knight BFS
12. All Nodes Distance K - Tree BFS with parent map
13. Clone Graph - BFS graph traversal
14. Walls and Gates - Multi-source BFS from gates

Tips & Tricks

• Always mark visited before adding to queue (not when polling)
• Use queue size loop for level-based processing
• Multi-source BFS: add all sources initially
• For shortest path, BFS guarantees minimum steps
• Direction arrays make grid traversal cleaner
• For tree levels, track level size at start of each iteration