Queues and BFS: Level-Order Traversal Templates

Role of Queue in BFS

Breadth-First Search (BFS) is like ripples spreading in water—starting from a source, it visits all neighbors at distance 1, then those at distance 2, and so on. The FIFO (First-In-First-Out) property of a queue is perfectly suited for this "layer-by-layer" progression.

Level-Order Traversal (LeetCode 102)

The most common BFS scenario is traversing a binary tree layer by layer.

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

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

    while (!q.isEmpty()) {
        int size = q.size();      // ← Count current layer's nodes (capture this now!)
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            // Add children of the processed node to the queue for the NEXT layer
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

Key Technique: Always record the current queue size (number of nodes in the layer) at the beginning of the while loop, and then use a for loop to process exactly that many nodes. Any new nodes added to the queue during this process will belong to the next layer.

{
  "type": "tree-traversal",
  "title": "Binary Tree Level-Order Traversal",
  "steps": [
    {
      "note": "Initial: Queue=[root=3], starting Layer 0",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [],
      "activeEdge": null
    },
    {
      "note": "Process Layer 0: Dequeue 3, Enqueue 9 and 20. Result: [[3]]",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [1],
      "activeEdge": [1, 2]
    },
    {
      "note": "Process Layer 1: Dequeue 9, Dequeue 20 (Enqueue 15 and 7). Result: [[3],[9,20]]",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [1, 2, 3],
      "activeEdge": [3, 4]
    },
    {
      "note": "Process Layer 2: Dequeue 15, Dequeue 7. Result: [[3],[9,20],[15,7]]",
      "treeNodes": [
        {"id": 1, "val": 3, "left": 2, "right": 3},
        {"id": 2, "val": 9, "left": null, "right": null},
        {"id": 3, "val": 20, "left": 4, "right": 5},
        {"id": 4, "val": 15, "left": null, "right": null},
        {"id": 5, "val": 7, "left": null, "right": null}
      ],
      "visitedNodes": [1, 2, 3, 4, 5]
    }
  ]
}

Variants of Level-Order Traversal

Zigzag Level Order (LeetCode 103)

Alternate directions for each layer (left-to-right, then right-to-left).

List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    boolean leftToRight = true;

    while (!q.isEmpty()) {
        int size = q.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (leftToRight) level.addLast(node.val);
            else level.addFirst(node.val); // Reverse insertion for even layers
            
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
        leftToRight = !leftToRight; // Flip direction
    }
    return res;
}

Minimum Depth of Binary Tree (LeetCode 111)

In BFS, the first leaf node encountered is guaranteed to be at the minimum depth.

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int depth = 0;

    while (!q.isEmpty()) {
        depth++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            // Shortest path found as soon as we hit a leaf
            if (node.left == null && node.right == null) return depth;
            
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return depth;
}

BFS on Graphs (LeetCode 994 Rotting Oranges)

Multi-Source BFS: Starting from multiple points simultaneously to find the shortest time to infect all "fresh" nodes.

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

    // Multi-source start: all initial rotten oranges enter the queue
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.offer(new int[]{i, j});
            if (grid[i][j] == 1) fresh++;
        }
    }

    int minutes = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.isEmpty() && fresh > 0) {
        minutes++;
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] pos = q.poll();
            for (int[] d : dirs) {
                int ni = pos[0] + d[0], nj = pos[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2; // Infect
                    fresh--;
                    q.offer(new int[]{ni, nj});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

BFS vs. DFS comparison

Memory Mnemonic: BFS is broad first (layer-order), while DFS is deep first (recursion).