Binary Tree Level Order Traversal

Level Order Traversal is the classic introduction to breadth-first search (BFS) on a tree. It is the move you reach for whenever a problem cares about depth — "the bottom row", "the rightmost node on each level", "the minimum depth".

The slow way first

You could traverse depth-first (recurse down each branch), tag every node with its depth, and then bucket the values by depth into groups. That works and is still O(n), but it is fiddly: you carry a depth parameter everywhere and assemble the groups at the end. BFS gives you the levels for free, in order, as you go.

The idea: a queue that drains one level at a time

A queue is first-in-first-out, so if you always push children as you pop parents, nodes come out in exactly the order you want: row by row. The trick that gives you the grouping is one line:

At the start of each pass, record len(queue) — that is the size of the current level. Pop exactly that many nodes into one group, pushing their children as you go. Those children form the next level, and they are already lined up behind the snapshot, so they do not leak into this group.

Walk through it

Step through the animation. The queue strip at the bottom shows who is waiting. We start with [3], pop it into level [3], and push 9, 20. The next pass snapshots size 2, pops both into [9, 20], and pushes 15, 7, 1, 8. The final pass pops all four leaves into [15, 7, 1, 8]. The queue is now empty, so we are done.

Pseudocode

if tree is empty: return []
queue = [root]
result = []
while queue is not empty:
    level = []
    size = number of nodes currently in queue   # snapshot!
    repeat size times:
        node = pop the front of the queue
        add node.val to level
        push node's left child  (if any)
        push node's right child (if any)
    add level to result
return result

The Python solution

from collections import deque
 
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

• deque gives O(1) popleft() — a plain list would be O(n) to pop from the front.
• for _ in range(len(queue)) is the heart of it: we freeze the level size before looping, so children pushed during the loop belong to the next level, not this one.
• level.append(node.val) collects this level's values; after the loop we push the whole level group into result.
• The outer while queue keeps going until every node has been visited.

Complexity

We touch each node exactly twice (one push, one pop), so time is O(n). The queue's peak size is the tree's widest level, which can be up to about n/2 nodes — so space is O(n).

When this pattern shows up

Practice