• The number of nodes in the tree is in the range [0, 2000]
• -1000 <= Node.val <= 1000
• Values within a level are ordered left to right
• Levels are returned top to bottom

Every traversal so far has been depth-first: commit to one branch, follow it to the bottom, then come back. That is the natural fit for recursion, and it is exactly wrong for this problem. A depth-first walk reaches a deep node on the left before a shallow node on the right, so nodes arrive with their depths interleaved. We need them grouped by depth, which means visiting all of depth 1, then all of depth 2, and so on — a fundamentally different order.

Think about what we know at the start: the level-0 list is just the root. And the level-1 list is exactly the children of everything at level 0. In general, each level is the collection of children of the level before it. That is a complete recipe, and it never needs to look further ahead than one step.

So keep a collection of "nodes discovered but not yet expanded." Take nodes out of it, and put their children in. The only question is the order in which nodes come back out — and it must be the order they went in, because that is what keeps level 1's nodes from being processed before level 0's are finished.

A structure with that behaviour is a queue: items are added at one end and removed from the other, so the first in is the first out — a waiting line. (Contrast the stack from Iterative Traversals, where the last in comes out first, which is precisely what produces depth-first order. The choice of container is the choice of traversal.)

Exploring a structure this way — everything one step away, then everything two steps away — is called breadth-first search, or BFS, and it works on graphs just as well as trees.

Run the queue loop naively and the values come out in the right order but as one flat stream, because the queue mixes generations: while we are expanding the last node of level 1, the first nodes of level 2 are already sitting behind it.

The fix is a small observation. At the exact moment we are about to start a new level, the queue contains precisely that level's nodes and nothing else — the previous level has been fully removed, and no node from the next level has been added yet. So take the queue's size at that instant, and that number tells us how many nodes to pull before the boundary. Children added during those pulls collect behind the line and become the next level's contents.

if root is None: return []
out, queue = [], deque([root])
while queue:
    level_size = len(queue)         # exactly the nodes at this depth, right now
    level = []
    for _ in range(level_size):     # pull exactly that many — no more
        node = queue.popleft()
        level.append(node.val)
        if node.left:  queue.append(node.left)    # joins the back, for the next round
        if node.right: queue.append(node.right)
    out.append(level)
return out

One detail on the queue itself: removing from the front of a plain array is O(K), because every remaining element shifts down, which would make the whole traversal O(N²) on a wide tree. Use a structure with constant-time removal at the front — collections.deque in Python, LinkedList/ArrayDeque in Java, or an array with a moving head index.

Watch the second round: after pulling 9 the queue held [20, 15, 7], three items — but the frozen count of 2 stopped the loop after 20, which is exactly where the level boundary belongs.

Every node is enqueued once and dequeued once, doing constant work each: O(N) time. The extra space is the queue, which holds at most one level, so it is O(W) where W is the tree's widest level — and in a full binary tree the bottom level holds about half the nodes, so W can be around N/2.

That is the real trade against depth-first search, and it is worth stating both directions. DFS costs O(H) memory, BFS costs O(W). On a chain-shaped tree, H = N while W = 1, so BFS wins outright. On a wide bushy tree, H ≈ log₂N while W ≈ N/2, so DFS wins outright. Neither is universally cheaper; it depends on the shape.

The recognition signal to carry forward: when a problem's answer is organised by depth or distance — per level, the first node at each depth, the shallowest something, the minimum number of steps — reach for a queue. Depth-first search can often be made to produce the same answer by tracking depth as a parameter, but it visits nodes in an order the problem does not care about, which makes early exits impossible. Every remaining problem in this section is this loop with one slot filled differently: Zigzag changes the order values are written into the level list, Right Side View keeps only the last node of each level, Maximum Width tracks positions instead of counts, and Populating Next Right Pointers links each node to the one behind it in the queue.