92. Binary Tree Level Order Traversal

BFS naturally visits nodes one level at a time. The trick to grouping the output by level is to snapshot the queue's size at the start of each iteration — at that moment the queue contains exactly the nodes of one level. Drain that many, enqueue their children, and you've completed one level cleanly.

Why the queue-size snapshot works

Standard BFS processes one node at a time and just dumps everyone into a flat list. To group by level we'd otherwise need depth tags on each entry. The size-snapshot trick avoids that: at the moment we start a new iteration of the outer loop, every node in the queue is from the same level. So we walk exactly len(queue) of them, gather their values, enqueue their children — and now the queue holds exactly the next level's nodes. Repeat.

Steps

1. Edge case: if root is None, return [].
2. Initialise queue = deque([root]) and result = [].
3. While queue is non-empty:
   • level_size = len(queue) — snapshot how many nodes are at the current level.
   • Initialise level = [].
   • Repeat level_size times: pop the front, append its value to level, enqueue its non-None children.
   • Append level to result.
4. Return result.

Walk-through

Tree:

       3
      / \
     9   20
        /  \
       15   7

Start: queue = [3], result = [].

Final result = [[3], [9, 20], [15, 7]]. ✓

Why we use deque instead of a list

deque.popleft() is O(1) — list.pop(0) is O(n) because it has to shift every other element down. For BFS that turns the algorithm from O(n) into O(n²). Always reach for collections.deque.

Edge cases

• Empty tree: the early-return guard handles it.
• Single node: one iteration, level [root.val], return [[root.val]].
• Skewed tree (linked list): every level has one node; we still visit each in O(1) per pop.

Complexity

• Time: O(n) — each node is enqueued once and popped once.
• Space: O(n) — at the widest level the queue may hold up to n/2 nodes (the bottom level of a complete binary tree).

import java.util.*;

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            result.add(level);
        }
        return result;
    }
}