102. Binary Tree Level Order Traversal

Most tree problems are naturally recursive, so it’s easy to reach for DFS on autopilot. This one is the exception that teaches breadth-first search: the answer has to come out row by row, and a queue is what tracks a frontier. It’s a cornerstone of the binary tree patterns, and the level-by-level trick here shows up again in shortest-path and grid problems.

The problem

Given the root of a binary tree, return its values grouped by depth — one inner list per level, read left to right, top to bottom. (Full statement on LeetCode.)

So a tree rooted at 3 with children 9 and 20, where 20 has children 15 and 7, returns [[3], [9, 20], [15, 7]]. An empty tree returns [].

Intuition: process one level before touching the next

A queue gives you nodes in the order you enqueued them, so if you push the root, then its children, then their children, you walk the tree top to bottom. The catch is grouping: a plain BFS hands you nodes in level order but flattened, with no boundary between rows.

The fix is one line of bookkeeping. At the start of each iteration, read queue.size() before you touch anything — that count is exactly how many nodes sit on the current level. Pop exactly that many, collect their values into one list, and enqueue their children as you go. The children you just added stay queued behind the current batch, so they become the next level’s snapshot.

$\text{levelSize} = |\text{queue}| \text{ at the moment the level begins}$

Freezing that size is the whole idea. Without it, the loop would keep pulling nodes past the row boundary, mixing depths into one list.

Solution

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;   // empty tree -> empty list

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();      // freeze the current row's width
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                // children join the queue behind the current level
                if (node.left != null)  queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);                 // one row done
        }
        return result;
    }
}

The if (root == null) guard matters: without it the first offer would enqueue a null and the loop would dereference it. Snapshotting levelSize into a local, rather than re-reading queue.size() in the loop condition, is what keeps each batch pinned to a single depth.

Complexity

	Time	Space
Queue BFS	$O(n)$	$O(n)$

Every node is enqueued and polled exactly once, so time is linear in the node count $n$. Space is dominated by the queue, which at its widest holds one full level — up to $n/2$ nodes in a balanced tree, so $O(n)$.

In an interview

Say “BFS with a queue, and I snapshot the size at each level” before writing a line — that sentence signals you know why the size freeze is there, which is the one detail interviewers probe. The classic trap is calling queue.size() inside the for condition instead of caching it; the queue grows as you enqueue children, so the loop overruns the boundary and levels bleed together. The other easy miss is the null-root case, which returns [] rather than [[]].

If they ask for a variation, the size-snapshot generalizes cleanly: zigzag order just reverses alternate rows, and Maximum Depth of Binary Tree is the same BFS with a level counter instead of a value list. For the recursive contrast, Same Tree shows how DFS handles structure the queue here handles iteratively. The binary tree patterns hub lays out when to pick BFS over DFS.

References

• LeetCode 102 — Binary Tree Level Order Traversal