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.
- The output groups, aggregates, or orders binary tree nodes by depth—such as per-level value lists, level averages, alternating zigzag order, or horizontal
nextpointers. - 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.
- Using
list.pop(0)instead ofcollections.deque.popleft()shifts all remaining elements on every dequeue, degrading total traversal time fromO(n)toO(n^2). - Marking graph or state-space nodes in
seenupon 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 Noneor blocked initial states (such as"0000" in deadendsinOpen the Lock) triggersAttributeErroronNone.valor permits illegal transitions out of an unreachable start.
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 resultdef 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 -1def 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