Tree BFS / Level Order

TL;DR

Tree BFS visits nodes in layers. You push the root onto a queue, then loop: pop the whole current layer in one go, collect its values, and push each node’s children onto the queue for the next pass. The queue grows wide before it grows deep — that’s the whole pattern.

The trick that makes the layer boundary clean is snapshotting the queue length at the top of each iteration. Whatever number you see is exactly the count of nodes on the current level; their children, which you’re appending as you go, belong to the next level and won’t be touched until the next outer iteration.

Reach for tree BFS whenever the question is phrased per-level: “level order”, “right side view”, “largest value in each row”, “minimum depth”, “populate next pointers across each level”, “zigzag traversal”. Anything that asks for a property of a layer — or a shortest path measured in edges — is BFS. If the question is about a single root-to-leaf path or a recursive subtree property, you want DFS instead.

When to reach for it

Signals that level-order BFS is the right move:

• The answer is per level — one value (or list) per row of the tree.
• The question asks for shortest depth (“minimum depth”, “first node matching X”) in an unweighted tree-shaped search space.
• You need to see neighbors at the same depth before going deeper — side views, level averages, level connections.
• The structure is a tree, DAG, or implicit graph (state-space search where each “level” = one move) and edges are unit cost.

Signals it’s not BFS: you need full root-to-leaf paths (DFS + backtrack), you’re computing a subtree-recursive property like height or balance (DFS), or edges have weights (Dijkstra, not BFS).

Flavor 1 — basic level order (LC 102)

Return a list of lists, one per level.

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)            # snapshot — this is the contract
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    return result

Worked example. A 4-node tree:

        1
       / \
      2   3
       \
        4

Step table. Q is the queue at the start of each iteration; level_size is the snapshot taken before the inner loop runs.

Notice in iteration 2 that node 4 got appended to the queue during the inner loop, but level_size = 2 was snapshotted before that, so the inner loop only ran twice. 4 waits for iteration 3.

Flavor 2 — right side view (LC 199)

Same skeleton; only the last node of each level survives.

def right_side_view(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:        # last node in this level
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

Trace on the same tree above. Iteration 1: pop 1, i == 0 == size-1, append 1. Iteration 2: pop 2 (skip), pop 3 (i == 1 == size-1), append 3. Iteration 3: pop 4, append 4. Result: [1, 3, 4].

The choice of “last in level” is what makes this a right-side view; flip to i == 0 and you get the left-side view. Same template, two different answers — that’s the leverage you get from level-order.

Flavor 3 — minimum depth (LC 111) and next-pointer connect (LC 116)

Minimum depth. Return the depth of the first leaf you see. BFS is strictly better than DFS here because the first leaf BFS encounters is guaranteed to be the shallowest one — you can early-exit.

def min_depth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth                   # first leaf wins
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

On the example tree, the first popped leaf is 3 at depth 2 — answer returns immediately, even though 4 exists at depth 3.

Connect next pointers (LC 116). Same level-snapshot skeleton, but inside the inner loop you wire node.next = queue[0] for every node except the last in its level.

def connect(root):
    if not root:
        return root
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i < level_size - 1:
                node.next = queue[0]       # peek at next node in same level
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
    return root

Trace on the tree above: at iteration 2, level is [2, 3]. After popping 2, queue[0] is 3 (since 4 hasn’t been pushed yet — wait, it has, because 2.left = 4 was just pushed). This is the gotcha: queue[0] after popping 2 is whatever is at the front, which after pushing 4 is 3 only if 3 was already there before 4 was pushed. It is — 3 was pushed in iteration 1. So 2.next = 3. Correct.

Why it works — the invariant

At the start of each outer iteration, the queue contains exactly all nodes at the current level, in left-to-right order, and nothing else.

That’s the entire correctness story. Snapshotting len(queue) at the top captures the size of the current level. The inner loop pops exactly that many nodes — the whole level — and pushes their children. Children of the current level are the next level, in left-to-right order, because we processed parents in left-to-right order and pushed left before right.

When the inner loop finishes, the queue once again contains exactly one level’s worth of nodes — the next one. Invariant restored. Loop until empty. Done.

Complexity

• Time: O(n). Every node is pushed and popped exactly once; the inner work per node is O(1).
• Space: O(w), where w is the maximum width of the tree (the largest level). For a balanced binary tree of n nodes, that’s O(n / 2) = O(n) in the worst case (the bottom level holds half the nodes). For a skewed tree, w = 1 and BFS uses O(1) extra space.

Compare to DFS, which is O(h) space where h is height — better for wide balanced trees, worse for skewed ones. Pick the traversal that matches your tree’s shape if memory is tight.

Common pitfalls

• Using list.pop(0) instead of deque.popleft(). A Python list pop from the front is O(n) because every other element shifts down — your whole BFS becomes O(n²). collections.deque gives you O(1) on both ends. Always.
• Forgetting to snapshot len(queue). If you write for _ in range(len(queue)) inline that’s fine, but while queue: without the inner for _ in range(level_size) mixes child nodes into the parent’s level — your “current level” list ends up with nodes from two depths.
• Mutating the queue mid-level. Don’t queue.clear(), don’t queue.extend(other_queue) inside the inner loop. You’ll either lose the next level entirely or duplicate it. Push children, that’s it.
• Accessing node.left / node.right without a None check. Every push must be guarded. A naked queue.append(node.left) when node.left is None will pop a None later and crash on node.val.
• Returning early on empty input. if not root: return [] (or 0, or [[]], depending on the problem’s contract). The inner loop assumes at least one node; without the guard you don’t crash, but you do return the wrong shape — [] vs [[]] matters.

Where you see this in production

• Browser DevTools — “Inspect element” tree expansion. Chromium’s DevTools renders the DOM as a collapsible tree; expanding a node level-by-level (when you Alt-click to expand all visible children) is a level-order walk over the live DOM. Same shape as LC 102.
• Language servers — AST traversal for syntax highlighting and folding ranges. TypeScript’s tsserver walks the AST in BFS order to compute per-line decorations and folding regions; the “fold all level-2 blocks” command literally snapshots level depth.
• Game engines — scene graph / transform updates in Unity and Unreal. When a parent transform changes, the engine BFS-walks its children to recompute world matrices level by level — parents must finish before children read their world transforms, which is exactly what level-order guarantees.
• The tree Unix command. Prints a directory tree with one row per level of indentation. The traversal is a queue-based BFS over the filesystem, with the level snapshot driving the indentation prefix.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.