Trees II — BFS / Level Order

Review boundary and corrected contracts

Snapshot len(queue) at the start of each level. Queue working space is O(maximum width); a returned list of all levels additionally stores O(n) values. A leaf has neither child: a missing child alone does not define minimum depth.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Learn breadth-first search on a tree, master the single trick — snapshotting the queue length at the top of each loop — that turns a flat BFS into a level-by-level traversal, and use it to solve level order, right side view, zigzag, and minimum depth.

Series: LeetCode — From Basics to Production-Ready · Session 23 / 65 · Phase 1 · Core patterns

Prerequisites

What you need first

You need the tree node model from L22 (a node with a value, a left child, and a right child) and the idea of a queue — a first-in-first-out line, which Python gives you as collections.deque. You do NOT need recursion here: BFS is iterative by nature. Everything else is built from scratch. This session pairs with L22 (DFS) to complete your tree-traversal toolkit and sets up graph BFS in L28.

Optional visual walkthroughs retained from the original lesson: level order, BFS variants, and right side view. The derivation and code below stand alone.

What this pattern IS

Breadth-first search (BFS) explores a tree by distance from the root: first the root, then everyone one step away, then everyone two steps away, and so on. Where DFS plunges down one branch to the bottom, BFS sweeps across the tree in horizontal layers. You implement it with a queue (FIFO): you take a node off the front, and you add its children to the back. Because children always go to the back, every node at depth d is fully processed before any node at depth d+1 is touched.

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

The naive version — pop one, push its children, repeat — visits nodes in the right order but gives you one flat list with no idea where one level ends and the next begins. The revelation of this session is a two-line fix: at the top of each outer iteration, record how many nodes are currently in the queue (n = len(queue)), then process exactly that many. Those n nodes are precisely one level. Everything they enqueue belongs to the next level and waits its turn. That single snapshot converts a flat walk into a clean level-by-level traversal, and almost every "hard" BFS tree problem is just "do something specific with each level" layered on top.

Boarding a plane by rows

Real: A gate agent calls rows in order: everyone in rows 1-5 boards, then rows 6-10, then 11-15. Before calling the next group they look at how many people are queued RIGHT NOW for the current group and let exactly those through. New arrivals join the back and wait for their group.

n = len(queue)   # how many belong to THIS level; process exactly n, the rest are next level

Deriving the level snapshot

Question: Why does recording len(queue) at the start of each iteration cleanly separate the tree into levels?

Premise: BFS with a FIFO queue processes nodes in non-decreasing order of depth.

Because: a node's children are enqueued when the node is dequeued, so children (depth d+1) always sit behind every node of depth d that is already waiting.

Premise: At the instant you finish enqueueing the root's level and are about to start a new pass, the queue contains EXACTLY the nodes of one depth and nothing else.

Because: you only added children after removing their parent, and all parents of the current level were themselves one level up.

Premise: So if you capture n = len(queue) before touching anything, those n nodes are the complete current level.

Because: no deeper nodes have been enqueued yet at that moment.

Premise: Looping exactly n times dequeues the whole level and enqueues the whole next level.

Because: each of the n nodes contributes its (0, 1, or 2) children to the back, forming the next level in order.

Premise: Repeating until the queue is empty walks the tree one full level per outer iteration.

Because: each outer pass consumes one level and produces the next.

Conclusion: The invariant: at the top of every outer loop, the queue holds exactly one level. Snapshot its length, process that many, and levels fall out for free.

The templates — annotated Python

from collections import deque
 
# ---- Template A: the canonical level-order skeleton ----------
def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        n = len(q)                     # SNAPSHOT: size of the current level
        level = []
        for _ in range(n):             # process exactly this level
            node = q.popleft()         # dequeue from the FRONT (FIFO)
            level.append(node.val)
            if node.left:  q.append(node.left)   # children -> back
            if node.right: q.append(node.right)  # they are the NEXT level
        out.append(level)              # one full level captured
    return out
 
 
# ---- Template B: flat BFS (no levels) — the naive base -------
def bfs_flat(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)           # single flat list, level info lost
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out
 
 
# ---- Template C: "act on each level" (right side view) -------
def right_side_view(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        n = len(q)
        for i in range(n):
            node = q.popleft()
            if i == n - 1:             # LAST node of this level = rightmost
                out.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
    return out

Lock in three things. First, use deque and popleft(), not a list with pop(0) — a list's pop(0) is O(n) because it shifts every remaining element, potentially turning an O(n) BFS into O(n^2) on a wide tree (a chain keeps the queue small). Second, the outer while q runs once per level; the inner for _ in range(n) runs once per node in that level — a loop inside a loop, but total work is still O(n) because every node is dequeued exactly once. Third, once you have Template A, most variants change only the per-level action: keep level, take its last element, or reverse it on alternate levels. Minimum depth additionally checks for a leaf and returns its level number; merely counting all iterations computes maximum depth. For level averages, append sum(level) / len(level) after each captured nonempty level.

Name: Ripples on a pond

Picture: Drop a stone on the root. Concentric rings spread outward — each ring is one level, all the nodes at the same distance. BFS processes ring by ring. At the start of an outer iteration the queue holds exactly the current ring; during its processing it can hold the remainder of that ring and part of the next; snapshotting its size tells you where the ring ends.

• Use a deque and popleft(); never list.pop(0).

• Snapshot n = len(q) at the top of each outer loop = the current level's size.

• Children go to the BACK; they are always the next level, never this one.

• First time you reach a node is via the SHORTEST path (fewest edges) — this is why BFS finds shortest distances.

Trigger: Any tree problem mentioning 'level', 'depth', 'each row', 'nearest', 'right/left side view', 'zigzag', or 'minimum depth'.

Memory / mnemonic

The whole pattern compresses to one chant: "SNAP the size, then serve the level." Snap = n = len(q) at the top of the loop; serve = loop n times dequeuing and enqueuing children. If you remember only that couplet you can rebuild level order from nothing.

For the shape of the code, picture two nested boxes: the outer box is "for each level", the inner box is "for each node in this level". Anything level-specific (the last node, the max, the sum, alternating direction) lives between the boxes — you decide it once per level, not once per node. And a peg for correctness: "queue = FIFO = fair" — first in, first out, so nearer nodes are always served before farther ones, which is exactly why the first time BFS reaches a node it did so by the shortest route.

Myth: You need a second queue, a depth counter stored on every node, or a marker element to know when one level ends and the next begins.

Truth: You need one integer captured once per outer iteration: n = len(q). Those n nodes ARE the current level; process exactly n and stop.

Why: People reach for extra machinery (two alternating queues, (node, depth) tuples, None sentinels) because the level boundary feels invisible. But the queue already contains exactly one level at the top of each pass, so its current length is the boundary — no extra state required.

Test: Write level order using a deque and the length snapshot. Tuples, a second queue, and sentinels are valid alternatives, but are unnecessary for this particular skeleton.

What reviewers actually ask

BFS on trees is heavily asked because a single skeleton spawns a whole family of problems, and reviewers can quickly escalate from "print the levels" to "do something clever per level" to see if you truly understand the snapshot or just memorised one solution.

• Binary Tree Level Order Traversal (102) · Medium · Practice selection. · probes: the queue-snapshot itself — do you produce a list-of-lists, one per level · follow-up: bottom-up order (107), or zigzag (103).
• Binary Tree Zigzag Level Order Traversal (103) · Medium · Practice selection. · probes: reverse alternate levels without reversing the traversal itself · follow-up: do it without a post-hoc reverse (append left vs right).
• Binary Tree Right Side View (199) · Medium · Practice selection. · probes: identify the last node of each level (i == n-1) · follow-up: left side view, or handle a right-sparse tree.
• Minimum Depth of Binary Tree (111) · Easy · Practice selection. · probes: the BFS early-stop guarantee — first leaf reached is the shallowest; this is not a universal speed advantage · follow-up: contrast with maximum depth (why DFS is fine there).
• Average of Levels in Binary Tree (637) · Easy · Practice selection. · probes: aggregate (sum/count) per level using the snapshot · follow-up: largest value in each row (515).
• Populating Next Right Pointers in Each Node (116) · Medium · Practice selection. · probes: link nodes within a level; can you do it with O(1) extra space using the established next-pointers · follow-up: the general tree (117).

Worked solutions

1. Binary Tree Level Order Traversal (102)

Plain words: return the node values grouped by level — a list of lists, top level first. A left-before-right DFS can append directly to out[depth] in one traversal, also O(n) time; no extra traversal is required. BFS instead makes the level boundary explicit in the queue.

from collections import deque
 
def levelOrder(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        n = len(q)                     # this level's size
        level = []
        for _ in range(n):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)              # one row done
    return out

Complexity: O(n) time (each node dequeued once), O(w) auxiliary queue space, plus O(n) returned output where w is the maximum width of the tree. At a boundary the queue is one level; during a pass it can contain parts of two adjacent levels, so its length is at most 2w, not necessarily exactly w. Follow-up: for bottom-up level order (107), build the list normally then reverse out, or out.appendleft(level) with a deque.

2. Binary Tree Zigzag Level Order Traversal (103)

Plain words: same as level order, but reverse the direction on every other level — left-to-right, then right-to-left, alternating. The clean move is to keep the traversal identical and just flip a boolean, reversing each captured level before appending (or, better, appending to the front on flipped levels).

from collections import deque
 
def zigzagLevelOrder(root):
    if not root:
        return []
    out, q, left_to_right = [], deque([root]), True
    while q:
        n = len(q)
        level = deque()                # deque so we can append to either end
        for _ in range(n):
            node = q.popleft()
            if left_to_right:
                level.append(node.val)     # normal order
            else:
                level.appendleft(node.val) # reversed, in O(1) each
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(list(level))
        left_to_right = not left_to_right  # flip for next level
    return out

Complexity: O(n) time, O(w) auxiliary queue space, plus O(n) returned output. The appendleft trick means you never pay a separate reversal — you build each level in its final orientation. Follow-up: reviewers may ask why you avoided level[::-1] (it's O(w) per flipped level, same asymptotically but an extra copy; appendleft on a deque is O(1)).

3. Minimum Depth of Binary Tree (111)

Plain words: the number of nodes on the shortest root-to-leaf path. BFS offers an early-stop guarantee: the first leaf you reach is shallowest. This can save visits versus a full DFS, but both are O(n) in the worst case and a wide BFS frontier can use more memory.

from collections import deque
 
def minDepth(root):
    if not root:
        return 0
    q, depth = deque([root]), 1
    while q:
        n = len(q)
        for _ in range(n):
            node = q.popleft()
            if not node.left and not node.right:  # first leaf reached
                return depth                      # = shortest, stop now
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        depth += 1                                # advanced one level
    return depth

Complexity: O(n) worst-case time, with possible early stopping; O(w) auxiliary queue space and O(1) scalar output. Contrast: for maximum depth (104), DFS is the natural fit because you must see every leaf anyway — there's no early-stop advantage.

Goal: Solve Right Side View (199) with the snapshot

Hint: Inside the inner loop, when i == n-1 you're at the rightmost node of the level — append its value.

Return the values you'd see looking at the tree from the right: the last node of each level, top to bottom. Reuse Template A but track the index i in for i in range(n); when i == n - 1 you're at the level's rightmost node, so append node.val. One tweak to the skeleton — proof that the snapshot generalises.

BFS versus DFS for tree problems

Decision: When to use BFS (level order) versus DFS for a tree problem.

Name: BFS (queue, level order)

Gain: Natural for anything per-level (level order, zigzag, side views, level averages) and finds the SHALLOWEST leaf first (minimum depth) so it can stop early.

Cost: O(w) memory — the widest level can hold up to ~n/2 nodes; more code than a one-line recursion for simple aggregates.

Pick: Problem mentions levels/rows/depth/nearest, or you need the shortest unweighted path.

Name: DFS (recursion)

Gain: Short code for subtree aggregates (height, sum, balance) and path problems; O(h) auxiliary memory. A wide balanced tree favors DFS space; a chain has h = n but w = 1.

Cost: No natural notion of 'level'; awkward for level-grouped output; can't early-stop on the shallowest leaf.

Pick: Subtree combines, path/return-vs-update problems, maximum depth.

Name: DFS with a depth parameter

Gain: Can produce level-grouped output by bucketing into out[depth]; keeps O(h) auxiliary stack space plus O(n) returned values.

Cost: Needs a depth argument and index-or-append bookkeeping; less obvious than BFS for level problems.

Pick: You want level grouping but a very wide tree makes BFS's O(w) queue too costly.

Verdict: Reach for BFS the moment a problem is defined per level or asks for the nearest/shallowest thing; reach for DFS for subtree combines and path problems. They are complementary halves of the tree toolkit, not competitors.

Where this shows up in production

A crawler can use BFS to explore increasing link distance from a seed, provided graph revisits are suppressed; actual crawlers may prioritize freshness or politeness instead. An org-chart UI can reveal one level at a time with this snapshot, though that does not establish how a particular UI or layout engine is implemented. The graph form (L28) finds minimum hop distances, for example degrees of separation. These are applications of the invariant, not measured production case studies.

You can now…

• Explain BFS as processing a tree by distance from the root using a FIFO queue.

• Write level-order traversal with the n = len(q) snapshot from memory.

• Say why deque/popleft is required and list.pop(0) is a hidden O(n^2) trap.

• State the invariant: at the top of each outer loop the queue holds exactly one level.

• Adapt the skeleton to right side view, zigzag, and level averages.

• Explain BFS's minimum-depth early-stop guarantee and its width-versus-height memory tradeoff.

• Give auxiliary queue space as O(w), and separately count any returned values.

Self-check (answer follows each question).

Recall · L23

Q: What single line turns a flat BFS into a level-by-level traversal?

A: n = len(q) captured at the top of each outer loop, then processing exactly n nodes — those n are precisely the current level.

Q: Why deque().popleft() instead of a list's pop(0)?

A: Removing the front of a list shifts its remaining entries. Summed over a wide tree this can make BFS O(n²), whereas deque.popleft() is O(1). A chain does not exhibit the quadratic case because its queue has constant size.

Q: What is the space complexity of level-order BFS and why?

A: O(w) auxiliary queue space: during a pass the queue spans parts of at most two adjacent levels, each at most w wide. Returning all levels additionally stores O(n) values; minimum depth returns only a scalar.

Q: What early-stop guarantee does BFS offer for minimum depth?

A: The first encountered leaf is shallowest because nodes are processed in nondecreasing depth. It may stop before visiting every node, but worst-case time remains O(n) and memory depends on width.

Q: In right side view, how do you pick the rightmost node of each level?

A: Track the index i in the inner loop; when i == n - 1 you're at the last (rightmost) node of that level, so record its value.

Q: Why is the first time BFS reaches any node guaranteed to be by the shortest path?

A: The FIFO queue processes nodes in non-decreasing distance from the source, so any node is dequeued (first reached) at its minimum hop-distance before any longer path to it is considered.

Stretch: true

Practice queue

• Binary Tree Level Order Traversal (102) — the core skeleton; anchor +7d.

• Average of Levels in Binary Tree (637) — aggregate per level.

• Binary Tree Level Order Traversal II (107) — bottom-up (reverse or appendleft).

• Binary Tree Right Side View (199) — last node per level; anchor +7d.

• Minimum Depth of Binary Tree (111) — first leaf = shallowest.

• Binary Tree Zigzag Level Order Traversal (103) — flip alternate levels.

• Find Largest Value in Each Tree Row (515) — max per level.

• Populating Next Right Pointers in Each Node (116) — link within levels; anchor +21d.

• BFS explores a tree by distance from the root using a FIFO queue (deque + popleft).

• Snapshot n = len(q) at the top of each loop — those n nodes are exactly one level.

• Children always go to the back of the queue; they form the next level, never this one.

• Auxiliary queue space is O(w); storing the complete level-order output adds O(n).

• BFS guarantees minimum depth at the first leaf, and minimum hop distance in an unweighted graph; it is not universally faster or smaller than DFS.

• Most variants (zigzag, side view, level average) change only what you do per level.

Corrective source notes

• Python deque documentation, pinned to CPython v3.14.0 — end operations are approximately O(1); list front operations move O(n) elements. Checked 2026-10-09.

• Breadth First Search - Algorithms for Competitive Programming — BFS discovers shortest paths by number of edges in an unweighted graph. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.