Binary Tree BFS

BFS on trees is about processing nodes level by level. The queue size at the start of a level is the invariant that keeps level boundaries clear.

Pattern A: Standard level order

Use when: you need lists per level or per-level processing.

Invariant: the queue contains exactly the nodes of the current level.

Skeleton:

queue = [root]
while queue not empty:
    size = len(queue)
    level = []
    repeat size times:
        node = pop front
        append node.val to level
        push node.left/right if exists
    append level to answer

Problems:

• binary-tree-level-order-traversal.

Pattern B: Zigzag traversal

Use when: you alternate left-to-right and right-to-left per level.

Invariant: level index parity defines direction.

Skeleton:

level = []
if leftToRight: append
else: prepend (or reverse at end)

Problems:

• binary-tree-zigzag-level-order-traversal.

Pattern C: Right side view

Use when: you need the last visible node per level.

Invariant: the last node processed in a level is the rightmost.

Skeleton:

for each level:
    for i in 0..size-1:
        node = pop
        if i == size-1: add node.val
        enqueue children

Problems:

• binary-tree-right-side-view.

Pattern D: Level averages

Use when: you need aggregate statistics per level.

Invariant: sum and count are for the current level only.

Skeleton:

sum = 0
for i in 0..size-1:
    sum += node.val
avg = sum / size

Problems:

• average-of-levels-in-binary-tree.

Pattern E: Next pointers by level

Use when: you need to link nodes across each level.

Invariant: you build the next level using a dummy head.

Skeleton:

cur = root
while cur:
    dummy = new Node(0)
    tail = dummy
    for node in level via next pointers:
        for child in [node.left, node.right]:
            if child: tail.next = child; tail = child
    cur = dummy.next

Problems:

• populating-next-right-pointers-in-each-node-ii.

When to use Tree BFS (checklist)

• You need per-level results or distance from root.
• The order of visiting nodes matters by level.

Common failures (checklist)

• Forgetting to capture level size before iterating.
• Mixing BFS and DFS assumptions (depth vs level).
• Not handling nil root gracefully.

Problem mapping

• binary-tree-level-order-traversal: standard BFS levels.
• binary-tree-zigzag-level-order-traversal: alternate direction.
• binary-tree-right-side-view: take last node per level.
• average-of-levels-in-binary-tree: sum and divide per level.
• populating-next-right-pointers-in-each-node-ii: connect levels with next pointers.