L23 · Trees II — BFS / Level Order

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

Prerequisites

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.

Deriving the level snapshot

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, silently turning your O(n) BFS into O(n^2). 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 what you do with level: keep it (level order), take its last element (right side view), reverse it on alternate levels (zigzag), or just count iterations (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.

What interviewers actually ask

BFS on trees is heavily asked because a single skeleton spawns a whole family of problems, and interviewers 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 · Amazon, Microsoft · 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 · Amazon, Microsoft · 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 · Amazon, Meta · 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 · Amazon, Meta · probes: why BFS beats DFS here — first leaf reached is the shallowest, so you can stop early · follow-up: contrast with maximum depth (why DFS is fine there).
• Average of Levels in Binary Tree (637) · Easy · Amazon · 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 · Amazon, Microsoft · 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. The brute-force temptation is to compute each node's depth (via a DFS) and bucket values by depth into a dictionary, which works but costs an extra pass and awkward indexing. The BFS insight is that the queue already hands you the levels in order.

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) space where w is the maximum width of the tree (the widest level sitting in the queue — up to about n/2 for the bottom level of a full tree). 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) space. The appendleft trick means you never pay a separate reversal — you build each level in its final orientation. Follow-up: interviewers 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. Here BFS genuinely beats DFS: the first leaf you reach is the shallowest one, so you can stop the instant you see a leaf — no need to explore the whole tree.

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, but often far less because you stop at the first leaf; O(w) space. Contrast: for maximum depth (104), DFS is the natural fit because you must see every leaf anyway — there's no early-stop advantage.

BFS versus DFS for tree problems

Where this shows up in production

Level-order BFS is the backbone of any "explore by nearest first" system. Web crawlers fan out breadth-first so they see pages closest to a seed before wandering deep. Rendering and layout engines walk the UI/DOM tree level by level to size parents before children. Org-chart and file-tree UIs that reveal one tier at a time are literally doing the queue snapshot. And the general graph form of exactly this loop (L28) is how unweighted shortest-path and "nearest reachable X" problems are solved — from social-network degrees of separation to flood-fill in image tools. The honest framing: whenever "distance in hops" or "one layer at a time" matters, BFS with the level snapshot is the tool.

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.