We have a binary tree, and we need to return its values grouped by level. All nodes at the same depth go into the same sublist, and within each sublist, nodes appear left to right. The result is a list of lists, where the first sublist contains only the root, the second contains all nodes at depth 1, and so on.

This is different from standard tree traversals (inorder, preorder, postorder) because those follow branch paths. Here, we need to process nodes "horizontally" across the tree. The core challenge is: how do we visit every node at depth d before visiting any node at depth d+1?

BFS answers it directly, since it visits nodes in order of distance from the root. DFS can also produce the grouping if each recursive call tracks the depth of the node it visits.

Key Constraints:

Intuition

DFS does not visit nodes level by level, but it can still produce the level grouping if every call knows the depth of the node it is visiting. Pass the depth as a parameter and append each node's value to result[depth]. The first time the traversal reaches a new depth, result has exactly depth sublists, so appending a fresh empty list at that moment keeps the indices aligned.

Ordering within each level also holds. The traversal recurses into the left subtree before the right one, so among nodes at the same depth, a node further to the left is visited earlier. Values therefore enter each level's sublist in left-to-right order.

Algorithm

Example Walkthrough

Code

The DFS version recovers the grouping from the depth parameter rather than from the order of traversal. BFS visits nodes level by level, so the traversal order matches the output directly. The next two approaches are both BFS; they differ in how they mark where one level ends and the next begins.

Intuition

BFS processes every node at depth d before any node at depth d+1, so a breadth-first traversal emits values in the order the output needs. What it does not provide on its own is the boundary between levels.

Two lists make that boundary explicit. current holds the nodes of the level being processed, and next collects their children. One pass over current produces one sublist of the result. When the pass finishes, next contains the entire following level in left-to-right order, because children were appended in the order their parents appear in current. Replacing current with next moves the traversal down one level, and the loop ends when a level produces no children.

Algorithm

Example Walkthrough

Code

The only overhead in the two-queue version is allocating a fresh node list for every level. A single queue can carry the same information: recording the queue's size before a level starts tells the loop how many dequeues belong to that level.

Intuition

Seed a queue with the root. At the start of each outer iteration, the queue holds exactly the nodes of one level, in left-to-right order. The invariant holds by induction: it is true at the start (the queue holds only the root), and each iteration dequeues every node of the current level while enqueueing their children in order, so the next iteration starts with exactly the next level.

The size snapshot is what preserves the invariant. Recording levelSize = queue.size() before the inner loop fixes how many dequeues belong to the current level. Everything enqueued during those dequeues belongs to the next level and stays in the queue for the following iteration.

A variant marks the boundary differently: enqueue a sentinel (such as null) after each level and start a new sublist whenever the sentinel reaches the front of the queue. The size snapshot gives the same separation without placing non-node values in the queue.

Algorithm

Example Walkthrough

Code