LC 102 · Medium · BFS · one row at a time

Binary Tree Level Order Traversal

The question groups nodes by level, or asks about the tree seen from the side.

Recognise it

Before any code, what in the question tells you this is the pattern?

The word "level", "row", "depth by depth", or anything about the shape of the tree seen sideways: the rightmost node per level, the average per level, the width. Depth-first recursion cannot group nodes by level without extra bookkeeping, so this is where you switch to a queue.

The brute force

Always have this one ready. It is the honest starting point, and it is what the real solution improves on.

Recurse depth-first, carrying the current depth, and append each value into a bucket for that depth. Then return the buckets in order.

O(n) time and O(n) space.

This one is genuinely fine, and worth saying so rather than dismissing it. It is a legitimate solution that many people prefer. The reason to learn the queue version anyway is that some questions in this family cannot be answered depth first without awkwardness: anything that needs to stop at a level, compare across a level, or find the shortest path in an unweighted graph. The queue generalises and the bucket trick does not.

The approach

The idea in plain language, before it becomes syntax.

Hold a queue of the nodes on the level you are currently reading. Take that entire level out, record it, and while doing so push the children, which together form the next level. Repeat until the queue is empty.

The single detail that makes this correct is measuring the level width before you start pushing. If you loop while the queue is non-empty without freezing the count, the children you push get read as part of the row you are still on, and every level after the first is wrong. Freezing the width is what separates the rows.

An alternative that avoids the counter entirely is to build the next level in a fresh list rather than pushing into the same queue, which is what the JavaScript version does. It is the same algorithm and the separation between rows becomes structural instead of arithmetic, which some people find easier to keep right under pressure.

A tree read row by row, with the queue holding exactly one level.Read one whole row, then the row it creates.3920157row 0: [3]row 1: [9, 20]row 2: [15, 7]queue holds exactly one rowFreeze the width before pushing children, or the row you are reading never ends.
Binary Tree Level Order Traversal: the idea in one picture.edit source
A queue holding exactly one level, with children forming the next.current rowtheir children, the next rowwidth = size(queue)read this BEFORE pushing anythingRead it inside the loop and the row you are on swallows the row you are building.
Freeze the width first, or the row you are reading never ends.

The algorithm

The same idea again, as steps you could follow with a pencil.

Flowchart for the level order loop.queue = [root]queue empty ?yesdonenowidth = size(queue)pop width nodes, push their children
Binary Tree Level Order Traversal: the loop, step by step.edit source
Time O(n)Space O(w), the widest level, which is up to n/2 at the bottom

The solution

Now the code, and why each decision in it is the way it is.

binary_tree_level_order_traversal
from collections import deque

def levelOrder(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):        # freeze the width before adding children
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

Each node enters and leaves the queue exactly once, so the time is linear. The space is the widest level rather than the height, and for a complete tree the bottom row holds about half the nodes, so O(n) in the worst case.

Children are checked for null when pushed, not when popped. Pushing nulls would mean every row contains gaps you then have to filter out, and the filtering is easy to get subtly wrong.

The empty tree returns an empty list. Returning a list containing an empty list is a common off-by-one that only shows up in the one test case people skip.

When depth-first is the right tool and when breadth-first is.depth firstheight, sums, ancestors, anythingbuilt from subtree resultsbreadth firstlevels, side views, shortest path,anything that stops earlyMemory differs too: depth first costs the height, breadth first costs the widest row.
Levels, shortest paths, and anything that stops early want the queue.

Where people slip

  • Freeze the width first: for _ in range(len(q)). Reading len(q) inside the loop after pushing children makes the current row swallow the next one.
  • Guard the children when pushing, not when popping. Pushing nulls means every level contains holes you then have to filter.
  • An empty tree returns an empty list, not a list containing an empty list. Check the root before the loop.

Your notes

What tripped you up here? Write it in your own words.

Where interviewers go next

Solve this one and the follow-up is usually a variation rather than a new idea. Knowing the connection is worth more than memorising each problem.

  • Right Side ViewLC 199Same loop, keep only the last value of each row. One line different.
  • Zigzag Level OrderLC 103Same loop, reverse alternate rows. Reverse the output row, never the queue.
  • Maximum WidthLC 662Carry an index with each node and measure first to last, because the gaps count.