LeetCode 102 · Trees

Binary Tree Level Order Traversal, explained with a picture

A family photo, one generation per row.

MediumTrees
▶ Watch it step by step

The problem

Return the values of a binary tree level by level, from top to bottom and left to right within each level.

Input:  [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]

Picture it

Picture a family photo with one generation per row. A queue holds everyone in the current row. We take them out one by one, write down their value, and put their children at the back of the queue. When the current row is used up, the queue holds exactly the next row.

How to recognise it

  • The output is grouped by depth: everything at level 0, then level 1, and so on.
  • Within a level the order is left to right, the order in which a queue naturally hands nodes out.
  • That is breadth-first search (BFS: visit all nodes at one distance before any farther ones). The extra twist is knowing where one level ends and the next begins.
  • Up to 2,000 nodes, so visit each node once.

Start with brute force

Collect one level at a time: for depth 0, 1, 2, ... walk the whole tree and keep the nodes at exactly that depth. Stop when a depth comes back empty.

def level_order_brute(root):
    def collect(node, d, out):
        if not node:
            return
        if d == 0:
            out.append(node.val)
        collect(node.left, d - 1, out)
        collect(node.right, d - 1, out)
    levels, d = [], 0
    while True:
        row = []
        collect(root, d, row)
        if not row:
            return levels
        levels.append(row)
        d += 1

The depth-first walk visits left before right, so each row comes out in the right order. But every level re-walks the tree from the root down to that level: O(n · h) time, where h is the height. A 2,000-node chain costs about 2 × 10^6 steps, and the recursion also exceeds Python's default limit of about 1,000 frames.

From brute force to the idea

  1. Find the waste. To reach level d, the brute force walks again through every level above it.
  2. Use a queue. A deque (double-ended queue) gives popleft() in O(1). If each node adds its children to the back, nodes come out in level order, left to right.
  3. Mark the level boundary. At the start of each round the queue holds exactly one full level and nothing else. So read len(q) once, pop exactly that many nodes into level, and push their children; the children wait for the next round.
  4. Save the row. After the inner loop, level is complete; append it to out.

This is the key idea: a BFS queue, processed in rounds of len(q) nodes, gives one level per round.

range(len(q)) is evaluated once, before the inner loop starts, so children appended during the loop do not change how many nodes this round pops.

The shown code needs from collections import deque. A plain list with pop(0) gives the same output but costs O(n) per pop.

The key idea

Breadth-first search with a queue, processing one level (queue length) at a time. O(n).

Python solution

def level_order(root):
    if not root:
        return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            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

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (one walk per level)O(n · h): each level re-walks the levels above itO(h): recursion stack, plus the output
BFS in rounds (shown code)O(n): each node enters and leaves the queue onceO(w): the queue holds at most one level plus children, w is the widest level (up to about n/2)

The output itself always takes O(n).

Edge cases

  • Empty tree: returns [], not [[]], thanks to the first check.
  • Single node: [[1]].
  • Chain of nodes: one value per level, for example [[2], [1], [0]].
  • Missing children: skipped by the if node.left checks, so None never enters the queue.
  • Deep chain of 2,000 nodes: works, because BFS uses a loop and no recursion.

Common mistakes

  • Popping until the queue is empty in the inner loop instead of len(q) times, which merges every level into one row.
  • Popping from the end (pop()) instead of the front: the container acts as a stack, and nodes from different levels get mixed into one row.
  • Pushing None children and then reading node.val on them.
  • Returning [[]] for an empty tree.
Your turn: zigzag order

Return the levels in zigzag order (LeetCode 103): the first level left to right, the next right to left, and so on. For [3, 9, 20, null, null, 15, 7] the answer is [[3], [20, 9], [15, 7]]. Describe your approach, then write it if you like.

Compare with our answer

Keep the same BFS in rounds. Only the saving step changes: reverse every second row before adding it. The queue order itself stays left to right.

from collections import deque

def zigzag(root):
    if not root:
        return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level if len(out) % 2 == 0 else level[::-1])
    return out

Time O(n), space O(w).

A strong answer mentions: reversing the collected row rather than changing the order children are pushed, using the row number to decide, and that the cost stays O(n).

Check what stuck

1. You must print a company org chart one management layer per line, top first. Which approach fits best?

2. Why does the shown code read len(q) before popping a level?

3. A learner replaces for _ in range(len(q)): with an inner while q:. Which tree still gets the right output?

Score 60% or more and the lesson is marked complete.