Binary Tree Level Order Traversal

Problem

Web crawlers and package dependency resolvers process nodes breadth-first to explore nearby neighbors before distant ones. Given the root of a binary tree, return the level-order traversal as a list of lists, where each inner list contains all node values at that depth.

    3
   / \
  9  20
    /  \
   15   7
→ [[3], [9, 20], [15, 7]]

Solution

Approach - BFS with a per-level size snapshot.

A plain queue-based BFS visits nodes in level order, but to group them into separate lists you need to know where one level ends and the next begins. The trick is to snapshot level_size = len(queue) at the top of each outer loop iteration, before enqueueing any children. At that instant the queue holds exactly the nodes of the current level and nothing else, so processing precisely level_size nodes consumes one full level. As you dequeue each of those nodes, you append its value to the current level's list and push its non-null children to the back - those children form the next level, and because you captured the count first, they stay out of the current pass.

Trace 3 -> (9, 20 -> (15, 7)). Seed the queue with [3]. Iteration one: level_size = 1, pop 3, record [3], enqueue 9 and 20. Iteration two: level_size = 2, pop 9 and 20 (the snapshot ignores 15 and 7 added mid-loop), record [9, 20], enqueue 15 and 7. Iteration three: level_size = 2, pop 15 and 7, record [15, 7], no children to add. Queue empties, returning [[3], [9, 20], [15, 7]]. A deque is essential here - popleft() is O(1), whereas a list's pop(0) is O(n) and would degrade the whole traversal to O(n^2).

Edge cases - A None root returns [] via the upfront guard. A single node returns [[val]]. Nodes are enqueued only when non-null, so the inner loop never dereferences a missing child.

Complexity - O(n) time, O(w) space - every node is enqueued and dequeued once, and the queue holds at most one level's width, up to O(n/2) for the bottom of a complete tree.