BFS & Level-Order Traversal

A different question: what's on each level?

DFS plunges down one branch to the bottom before touching the next. But many tree questions are about breadth, not depth: "what does the tree look like row by row," "what's the value at each level," "how far is the nearest leaf." For those, you want to visit all of level 0, then all of level 1, then all of level 2 — the root, then its children, then its grandchildren. That is breadth-first search (BFS), and on a tree it is also called level-order traversal.

DFS was powered by a stack (LIFO — last in, first out), whether the call stack or an explicit one. BFS is powered by a queue (FIFO — first in, first out). That one swap, stack for queue, is the entire difference between "go deep" and "go wide," and the reason is worth seeing precisely.

Why a queue produces level order

The invariant: process nodes in the order they were discovered. Start by putting the root in the queue. Then repeat: remove the front node, process it, and add its children to the back.

Watch what the FIFO discipline guarantees. The root (level 0) is discovered first, so it's processed first. Processing it enqueues its children (level 1) at the back. Those level-1 nodes sit behind nothing, so they come out next — before any level-2 node, because level-2 nodes are only enqueued while processing level-1 nodes, which happens later and adds to the back. A node at level k is always enqueued before any node at level k+1 (its discovery requires processing a level-k parent first) and FIFO preserves that order on the way out. So nodes exit the queue level by level, left to right. The queue sorts discoveries by depth automatically — that's the whole trick.

Queue trace: [1] → process 1, enqueue 2,3 → [2,3] → process 2, enqueue 4,5 → [3,4,5] → process 3, enqueue 6 → [4,5,6] → process 4,5,6. Output order: 1, 2, 3, 4, 5, 6 — exactly level by level.

Tracking level boundaries: the size snapshot

Plain BFS gives you nodes in level order but flattened — it doesn't tell you where one level ends and the next begins. Most level-order problems (next lesson's "return a list per level," right-side view two lessons on) need that boundary. The clean trick: at the top of each level, snapshot the current queue size.

Picture a theme-park staff member letting people onto a ride in batches. Before waving anyone through, they count exactly how many people are currently standing in the roped-off queue — say, 14 — and let through precisely that many, no more. Anyone who joins the line while those 14 are boarding doesn't get counted in this batch; they're next batch's problem. That upfront headcount is the whole trick: it draws a hard line between "this batch" and "whoever shows up after," even though new people keep joining the same physical line the whole time.

The key observation: at the instant you're about to start a new level, the queue contains exactly the nodes of that level and nothing else — every previous level has been fully dequeued, and no node from the next level has been enqueued yet (those get added only as you process this level). So the queue's current length is this level's node count. Grab that number, then dequeue exactly that many nodes, processing them as one level, enqueuing their children (the next level) for the following round:

from collections import deque

def level_order(root: TreeNode | None) -> list[list[int]]:
    levels: list[list[int]] = []
    if root is None:
        return levels
    queue: deque[TreeNode] = deque([root])
    while queue:
        level_size = len(queue)          # queue == exactly this level, right now
        current: list[int] = []
        for _ in range(level_size):      # dequeue precisely one level's worth
            node = queue.popleft()
            current.append(node.val)
            if node.left:                # enqueue children = the NEXT level
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(current)           # one level finished
    return levels

Capturing level_size before the inner loop is load-bearing: the loop enqueues the next level's nodes into the same queue as it runs, so len(queue) grows during the loop. Reading it once, up front, freezes the count at "this level only." That single snapshot is the standard idiom for every level-boundary problem in this module.

Trace it on the tree diagrammed above (root 1, children 2 and 3, 2's children 4 and 5, 3's child 6). Queue starts [1]; snapshot level_size = 1. The inner loop runs once: dequeue 1, enqueue its children — queue is now [2, 3]. One level recorded: [1]. Next iteration: snapshot level_size = 2 (the queue's current length, re-read fresh). The inner loop runs twice: dequeue 2, enqueue 4 and 5 (queue: [3, 4, 5]); dequeue 3, enqueue 6 (queue: [4, 5, 6]). Level recorded: [2, 3] — note the loop stopped at exactly 2 dequeues, never touching the 4, 5, 6 it just enqueued, because level_size had already been frozen at 2 before any of them existed. Final iteration: snapshot level_size = 3, dequeue all of 4, 5, 6, enqueue nothing (all leaves). Level recorded: [4, 5, 6]. Queue now empty, loop ends. Three levels, exactly as the tree's three rows demand.

(Python note: use collections.deque, whose popleft is O(1). A plain list's pop(0) is O(n) because it shifts every remaining element — using it would silently turn the whole traversal into O(n²). TypeScript's Array.shift has the same O(n) hazard; for large inputs a head-index pointer or a real queue avoids it. The complexity claims below assume an O(1) dequeue.)

DFS vs. BFS: the memory profiles, argued

Both visit every node once, so both are O(n) time. Their space is where they diverge, and the difference is not arbitrary — each holds a different "frontier" of the tree:

• DFS holds a root-to-node path. Its stack (call stack or explicit) contains the chain of ancestors of the node it's currently at — one entry per level, from the root down. The most it ever holds at once is the tree's height. So DFS space is O(h).
• BFS holds an entire level. Its queue, at its fullest, contains all the nodes of the widest level (plus possibly the tail of the previous one), because it must remember every node on the current row in order to visit their children next. So BFS space is O(w), where w is the maximum width of the tree.

Now the consequences, which are opposite for the two tree shapes:

• A balanced tree is wide at the bottom: the last level holds up to n/2 of the n nodes. (This falls out of the same doubling the Terminology lesson used for height: a full tree of height h has n = 2⁰ + 2¹ + ⋯ + 2ʰ = 2ʰ⁺¹ − 1 nodes total, and its last level alone holds 2ʰ of them — roughly half of n, since 2ʰ⁺¹ is barely more than twice 2ʰ. Every level above the last combined holds only as many nodes as the last level holds by itself.) So BFS peaks at O(n) space, while DFS uses only O(log n) (the height). Here DFS is far cheaper.
• A degenerate tree (a single chain, effectively a linked list) has width 1 at every level but height n. So BFS holds only O(1) at a time, while DFS's stack grows to O(n) (and risks a recursion-limit crash). Here BFS is far cheaper.

Neither dominates; they trade width for height. The rule of thumb that falls out: BFS's O(w) hurts most on the bushy trees where DFS thrives, and DFS's O(h) hurts most on the stringy trees where BFS thrives. Choose by what the problem needs (level structure → BFS; path/subtree combination → DFS), and be aware of the space profile the tree's shape will hand you.