Dashboard/Coding patterns/21. Tree Breadth-First Search

CODING PATTERNS · LESSON 21 OF 28 · 43 MIN VIDEO · 14 PROBLEMS

Tree Breadth-First Search

Module Progress (0 / 14 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (43 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Tree Breadth-First Search — How the Pattern Works

Breadth-First Search (BFS) traverses a tree or unweighted graph radially outward in concentric waves using a First-In-First-Out (FIFO) queue (collections.deque). It maintains the invariant that all nodes at distance d from the source are dequeued and processed before any node at distance d + 1 is dequeued, because newly discovered children always join the back of the queue behind the active frontier. Snapshotting len(queue) at the start of each outer iteration isolates exact depth levels in a single O(n) pass—reducing O(n * h) repeated root-to-depth walks to O(n)—and guarantees that the first arrival at any target state discovers a shortest path without exponential path enumeration.

WHEN TO USE THIS PATTERN
  • The output groups, aggregates, or orders binary tree nodes by depth—such as per-level value lists, level averages, alternating zigzag order, or horizontal next pointers.
  • The prompt asks for the minimum number of moves, turns, or single-step transitions to reach a target state in an unweighted graph or implicit state space (e.g., Word Ladder, Open the Lock).
  • Traversal states carry cumulative positional or probabilistic metadata one step per wave, such as (node, row, col) coordinates for vertical column grouping or (node, prob) for discrete-time random walks.
  • A tree or grid problem asks for the closest vertex to a target set, tree diameter endpoints via two-pass BFS, or minimum aggregate Manhattan-path distance across multiple sources.
COMMON INTERVIEW PITFALLS
  • Using list.pop(0) instead of collections.deque.popleft() shifts all remaining elements on every dequeue, degrading total traversal time from O(n) to O(n^2).
  • Marking graph or state-space nodes in seen upon dequeue rather than immediately upon enqueue allows duplicate frontier states to flood the queue within the same wave, causing memory blowup and Time Limit Exceeded.
  • Reading len(queue) after pushing children—or reversing the queue itself for zigzag order—corrupts level boundaries and scrambles child order for all deeper levels.
  • Failing to guard against root is None or blocked initial states (such as "0000" in deadends in Open the Lock) triggers AttributeError on None.val or permits illegal transitions out of an unreachable start.
Level-by-Level Tree Traversal (Queue Size Snapshot)Grouping, aggregating, or transforming binary tree nodes separately per depth level.
def bfs_levels(root):
    result, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            for child in (node.left, node.right):
                if child:
                    queue.append(child)
        result.append(level)
    return result
Shortest-Path State-Space BFSFinding minimum transitions from `start` to `target` in an unweighted graph or state space with cycle/duplicate prevention.
def shortest_steps(start, target, get_neighbors):
    queue, seen = deque([(start, 0)]), {start}
    while queue:
        cur, dist = queue.popleft()
        if cur == target:
            return dist
        for nxt in get_neighbors(cur):
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, dist + 1))
    return -1
O(1)-Space Level Walk via Next PointersLinking same-level neighbors in a perfect binary tree by traversing already-linked parent `next` chains instead of an explicit queue.
def connect_perfect_tree(root):
    leftmost = root
    while leftmost and leftmost.left:
        node = leftmost
        while node:
            node.left.next = node.right
            if node.next:
                node.right.next = node.next.left
            node = node.next
        leftmost = leftmost.left
    return root
🔒 PRO PROBLEMTarget: O(n) time O(1) extra space

03. Populating Next Right Pointers in Each Node

Pattern Trigger: link same-level neighbors → walk the level above

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Think back to the tree we just walked. In breadth first order, which node comes out fourth?