Patternwise

Tree BFS (Level Order)

Process the tree floor by floor using a queue.

Brute force
O(n·h) — re-walk from the root for each depth
With the pattern
O(n) — each node enqueued once
Extra space
O(w) — widest level (up to n/2)

In plain English

“Picture a family tree photo shoot: first the grandparents stand in a row, then all their children, then all the grandchildren. A helper with a clipboard calls each person forward, and as they step up they point to their own kids, who join the back of the waiting line.”

Why it's fast

A queue naturally outputs nodes in order of their distance from the root. By snapshotting len(queue) at the start of each round, you know exactly which nodes belong to the current level, so per-level questions (right side view, averages, zigzag) need no extra depth bookkeeping. Every node is enqueued and dequeued once: O(n).

Spot it when the problem says…

  • level order / level by level
  • right side view / left view
  • minimum depth / shortest path in a tree
  • average / max of each level
  • zigzag order
  • connect nodes on the same level

Visualize

Level-order traversal

Return the tree's values level by level, top to bottom.

831016144713

queue (front → back)

front8back

level

[]

result

[]
01/24

Start with just the root in the queue. Blue = waiting in queue, green = done.

pythonline 3
1from collections import deque2def level_order(root):3    result, queue = [], deque([root])4    while queue:5        level = []6        for _ in range(len(queue)):   # exactly one level7            node = queue.popleft()8            level.append(node.val)9            for child in (node.left, node.right):10                if child: queue.append(child)11        result.append(level)12    return result

How to apply it

  1. 01Put the root in a deque (return early if root is None).
  2. 02While the queue isn't empty, record size = len(queue) — that's one level.
  3. 03Pop size nodes, handle each, and append their non-null children.
  4. 04After the inner loop, finalize that level's result.

Variations you'll meet

Level-order traversal

The visualizer's example.

python
from collections import dequedef level_order(root) -> list[list[int]]:    if not root:        return []    res, q = [], deque([root])    while q:        level = []        for _ in range(len(q)):          # exactly this level            node = q.popleft()            level.append(node.val)            if node.left:                q.append(node.left)            if node.right:                q.append(node.right)        res.append(level)    return res

Right side view

Keep only the last node popped in each level.

Zigzag

Build each level normally, then reverse every other level (or append to a deque from alternating ends).

Min depth / early exit

The first leaf you dequeue is at the minimum depth — BFS can stop immediately, unlike DFS.

Common mistakes

  • Using list.pop(0) instead of deque.popleft() — O(n) per pop.
  • Reading len(q) inside the loop condition, so it changes as children are added.
  • Appending None children and then crashing on .val.
  • Forgetting the empty-tree case.

Practice ladder

Easy → hard. Tick them off as you go.

Think you've got it?

Let the AI interviewer throw a Tree BFS (Level Order) problem at you and grade how you explain it.

Mock interview