Binary Tree Level-Order Traversal (BFS), in depth: the size-snapshot invariant, four ways to mark levels, the variant family and the real O(W) memory cost

Why a queue visits nodes by depth

Start with plain breadth-first search: put the root in a first-in, first-out queue; repeatedly remove the front node, record it, and append its non-null children. Why does this visit nodes in order of depth? Because of a simple property of the queue: at any moment, the depths of the nodes in it, read front to back, are non-decreasing and differ by at most one. It holds initially (one node). When you remove a node of depth d, everything behind it has depth d or d+1, and you append children of depth d+1 at the back, so the property survives. A queue with that property releases every depth-d node before any depth-(d+1) node.

That gives you the right order, but most problems want the output grouped into rows. The standard trick is the size snapshot: at the start of each outer iteration, read the queue's length and process exactly that many nodes.

Invariant. At the top of the outer loop, the queue contains exactly the nodes at depth d, in left-to-right order. Proof by induction: true for d = 0. Assume it for d and let k be the queue length. Popping k nodes removes exactly the depth-d nodes, and the only nodes appended meanwhile are their children, which are all the depth-(d+1) nodes, appended in left-to-right parent order and left-before-right child order. So after k pops the invariant holds for d+1. The snapshot must be taken before the inner loop; reading the length on every inner iteration would include children appended during the level.

Reference implementations

The reference implementation in Python uses collections.deque, whose popleft is O(1).

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        size = len(q)                 # snapshot: exactly one level is queued
        row = []
        for _ in range(size):
            node = q.popleft()
            row.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(row)
    return out

The Java version uses ArrayDeque and proper generics. ArrayDeque is faster than LinkedList for this workload because it is a contiguous ring buffer, but it rejects null elements, so you must never enqueue a null child.

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();                    // snapshot before the inner loop
        List<Integer> row = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            row.add(n.val);
            if (n.left != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        out.add(row);
    }
    return out;
}

Worked trace

Trace the tree in the diagram: root 1 with children 2 and 3; node 2 has children 4 and 5; node 3 has a right child 6; node 5 has a left child 7.

The result is [[1], [2, 3], [4, 5, 6], [7]]. Every node is enqueued once and dequeued once, so the work is proportional to n = 7. The queue peaked at three nodes, the width of depth 2. Note that 7 was appended during level 2's processing but was not popped until level 3, exactly because the size snapshot was 3, not 4.

Four ways to mark a level

The size snapshot is one of four ways to know where a level ends. The others are worth knowing because each fits some situations better.

Null sentinel. Push a marker after the root; whenever you pop the marker, the current level is done, and if the queue is non-empty you push another marker. It works, but in Java it fails at runtime with ArrayDeque (null is rejected) and forces LinkedList or a dedicated marker object, and the termination check is easy to get wrong.

Two lists. Keep the current level in one list and build the next level in another, then swap. There is no queue at all, which makes the level boundary obvious and makes per-level operations such as reversal trivial.

def level_order_lists(root):
    out, level = [], [root] if root else []
    while level:
        out.append([n.val for n in level])
        level = [c for n in level for c in (n.left, n.right) if c]
    return out

DFS carrying depth. A preorder walk that passes the depth produces the same grouping, because preorder visits each level's nodes left to right.

def level_order_dfs(root):
    out = []
    def go(node, d):
        if not node:
            return
        if d == len(out):
            out.append([])
        out[d].append(node.val)
        go(node.left, d + 1)
        go(node.right, d + 1)
    go(root, 0)
    return out

The variant family

Almost every level-order problem is the reference loop with a different row action.

• Zigzag. Alternate left-to-right and right-to-left by row. Do not change the enqueue order; build the row normally and reverse it on odd depths, or write into a deque with appendleft on odd depths. Changing the order children are enqueued breaks the next level.
• Per-level aggregates. Average, maximum or sum per row: replace row.append with an accumulator. Use a wide numeric type for sums.
• Bottom-up order. Collect rows top-down, then reverse the outer list. Inserting at the front of a Python list on every level costs O(levels squared).
• Right side view. Keep the last node of each row. The full family of views is covered in tree views.
• N-ary trees. Replace the two child checks with a loop over node.children; nothing else changes.
• Minimum depth. Return the current depth the first time you pop a leaf. BFS can stop early here, which DFS cannot, so on a tree with a shallow leaf and a deep spine BFS touches far fewer nodes.
• Maximum width including gaps. Enqueue (node, index) with children at 2i and 2i+1 and take last minus first plus one per row. Indices double per level and overflow fixed-width integers on deep, sparse trees, so re-base each row by subtracting the row's first index.
• Next pointers. Linking each node to its right neighbour is a row action too; populating next pointers shows how to then drop the queue entirely.

def zigzag(root):
    out, q, d = [], deque([root] if root else []), 0
    while q:
        row = deque()
        for _ in range(len(q)):
            n = q.popleft()
            (row.append if d % 2 == 0 else row.appendleft)(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        out.append(list(row)); d += 1
    return out

Complexity and the width bound

Time is O(n): each node is enqueued and dequeued once and each edge examined once. Memory is where people are imprecise. The queue holds at most one full level plus part of the next, so the bound is O(W), the maximum width. How large is W? On a perfect tree with n = 2^(h+1) - 1 nodes, the last level holds 2^h = (n+1)/2 nodes, so BFS needs memory proportional to half the tree. On a degenerate, list-shaped tree, W is 1. DFS has the opposite profile: its stack is O(h), which is about log n for a balanced tree and n for a degenerate one.

The output itself is O(n) when you return all rows, which dominates both. The queue bound matters when you stream rows to a consumer instead of materialising them, for example serialising a very large tree level by level to disk.

A concrete comparison makes the difference tangible. A perfect tree of depth 19 has about one million nodes; BFS holds up to 524,288 references at its widest level, while DFS holds a stack of 20 frames. A degenerate chain of one million nodes reverses the picture: BFS holds one node, and recursive DFS overflows long before the bottom. Real trees fall between these extremes, so pick the traversal by the shape you expect rather than by habit.

Failure modes

These are the bugs that show up in reviews and on judges.

• Using list.pop(0) in Python. It shifts every element, so a wide level costs O(W) per pop and the traversal becomes O(n W), roughly O(n squared) on bushy trees. Use deque.popleft.
• Reading the size inside the loop. for i in range(len(q)) in Python evaluates once and is fine; a Java for (int i = 0; i < q.size(); i++) re-reads it and mixes levels.
• Missing the null root. Return an empty list before enqueuing, or the first dereference crashes.
• Enqueuing null children. Crashes with ArrayDeque and wastes work elsewhere; check before enqueuing.
• Recursion depth in the DFS variant. Python's default limit is about 1,000 frames, so a degenerate tree of 10,000 nodes raises RecursionError. Use the iterative BFS.
• Changing enqueue order for zigzag. Reversing child order on odd rows produces wrong output from the third level on.
• Width index overflow. Unbounded index growth on deep trees; re-base per row.

Trade-offs: BFS or DFS

Choose BFS when the answer is defined by levels, when you can stop at the first match near the root (minimum depth, nearest leaf), or when the tree is deep and narrow and recursion would overflow. Choose DFS with depth when the tree is wide and shallow and memory matters, or when the per-level result also needs subtree information computed on the way back up, as in tree dynamic programming. Both visit every node in the full traversal, so neither wins on time. For the general graph version, where a visited set is needed because nodes can be reached twice, see BFS and DFS; trees need no visited set because each node has exactly one parent.

What to do next

1. Implement the size-snapshot version from memory in your main language and test it on an empty tree, a single node, a degenerate chain and a perfect tree of depth 4.
2. Write the DFS-with-depth version and check that both produce identical output on random trees.
3. Solve zigzag, per-level maximum and minimum depth by changing only the row action.
4. Measure peak queue length on a perfect tree of 2^16 - 1 nodes and confirm it is 32,768.
5. Replace deque with list.pop(0) and time a perfect tree of depth 18 to see the quadratic cost for yourself.
6. Extend the traversal to graphs with a visited set and compare it to the animated walkthrough in BFS, animated.