Algorithm

Binary Tree Level Order Traversal

Trees Pattern

Binary Tree Level Order Traversal

Given the root of a binary tree, return its values grouped by depth: a list of lists, where the first inner list holds the root, the second holds all nodes one level down read left to right, and so on. The grouping matters — a single flat list of the same values is not an accepted answer. An empty tree returns an empty list of levels.

CONSTRAINTS
  • 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
EXAMPLE 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Three depths, three groups. 15 and 7 land in the same group despite both being 20's children, because grouping is by depth rather than by parent.
EXAMPLE 2
Input: root = [1,2,3,4,null,null,5]
Output: [[1],[2,3],[4,5]]
4 and 5 sit at the same depth under different parents, and 4 comes first because its parent is further left. The gaps between them contribute nothing to the output.
EXAMPLE 3
Input: root = [1,2,null,3]
Output: [[1],[2],[3]]
A chain gives one node per level, so every group holds a single value.
EXAMPLE 4
Input: root = []
Output: []
No nodes means no levels — an empty outer list, not a list containing an empty list.
Is a flat list of values acceptable?
No, the levels must be separated. Producing the right values in the right order but in one list is the most common near-miss here.
How should missing children be treated?
They are skipped entirely — no placeholder appears in the output. A level's list holds only the nodes that actually exist.
Can this be done with recursion instead of a queue?
Yes: a depth-first walk that appends each value to the list for its depth works fine and gives the same result. The queue version is preferred when you need levels processed strictly in order, such as for an early exit at the first level satisfying some condition.
What is the memory cost?
The queue holds at most one level at a time, so it is proportional to the tree's widest level — which for a bushy tree can be about half of all nodes.

We want the values grouped by depth: level 0 (the root), then all of level 1 read left to right, then level 2, and so on.

text
        3            level 0:  [3]
       / \
      9   20         level 1:  [9, 20]
         /  \
        15   7       level 2:  [15, 7]

A recursive (depth-first) walk is the wrong tool: it dives down one branch to the bottom before touching a shallow node on another branch, so depths arrive jumbled. We need to sweep across each level fully before going deeper.

Sweep level by level with a queue

The key fact: level 1 is just the children of level 0, level 2 is the children of level 1 — each level is the children of the one above. So keep a waiting line of "found but not yet expanded" nodes. Pull one off the front, drop its children at the back. Since we always remove from the front and add at the back — first in, first out — nodes come out in the order they were discovered, which keeps a whole level together before the next starts.

That first-in-first-out structure is a queue, and exploring a tree this way — everything one step away, then everything two steps away — is breadth-first search (BFS).

Cut the stream into levels

Run the queue plainly and the values come out correct but as one flat stream — the queue mixes generations. The fix is one observation: right before a level starts, the queue holds exactly that level's nodes and nothing else. So freeze the queue's size at that instant, pull exactly that many, and whatever children pile up behind them become the next level.

text
queue, level by level  (freeze the size, then pull that many):

 [3]            size 1 -> pull 3;  push 9,20      -> level [3]
 [9, 20]        size 2 -> pull 9, 20; push 15,7   -> level [9, 20]
 [15, 7]        size 2 -> pull 15, 7              -> level [15, 7]
 []             empty -> done
python
if root is None: return []
out, queue = [], deque([root])
while queue:
    level_size = len(queue)         # exactly this depth's nodes, 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 next round
        if node.right: queue.append(node.right)
    out.append(level)
return out
Crucial Notecapture level_size before the inner loop and never re-read it. The queue keeps growing as children are appended, so a loop written against the live length would run straight into the next level and never draw a boundary. Freezing the count is the whole trick that turns flat BFS into level-grouped BFS. (Also: use a real queue with O(1) front removal — deque / ArrayDeque — not front-pop on a plain array, which shifts every element and makes the walk O(N²).)
Cost, and when to reach for BFS

Each node is enqueued once and dequeued once: O(N) time. The queue holds at most one level, so O(W) space, where W is the widest level (in a full tree the bottom level is about half the nodes).

That's the real trade against depth-first: DFS costs O(H) memory, BFS costs O(W). On a chain H = N but W = 1, so BFS wins; on a bushy tree H ≈ log₂N but W ≈ N/2, so DFS wins. Neither is always cheaper — it's about shape. The signal to reach for a queue: when the answer is organised by depth or distance — per level, the first node at each depth, the shallowest/nearest something, the fewest steps.

Interactive Strategy Visualization

Level Order Traversal

Horizontal BFS Logic

3920157
Queue & Path
FIFO Queue
3
[]
Result Set

"Snapshot queue size to separate levels."

Strategy

Process by 'snapshotting' queue size. each level is handled completely before the next begins.

"Generational BFS traversal."

O(N × H) Repeated Depth-Limited Walks
→
O(N) Time · O(W) Space Queue With Frozen Level Size