Binary Tree Level Order Traversal

The key insight: at the start of each outer loop, queue.size() equals the number of nodes at the current level. Process exactly that many nodes, then move to the next level.

Implementation steps:

• Enqueue the root.
• While the queue is non-empty, snapshot levelSize = queue.size().
• Dequeue levelSize nodes, collect their values, enqueue their children.
• Add the level's values to the result list.

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(); // nodes at this level
        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;
}

Trace through Example 1: root = [3,9,20,null,null,15,7]

• Time: O(n). Each node is enqueued and dequeued exactly once.
• Space: O(n). The queue holds at most n/2 nodes (widest level of a complete binary tree).