Tree breadth-first search

Problem

Some questions are about levels: group the values by depth, show what you would see standing to the right of the tree, find the level with the most nodes, or find everything exactly k steps from a given node. Depth-first search can answer these by carrying the depth as a parameter and filing values into per-level buckets, but the answer then comes out in an awkward order and you cannot stop early at the first level that satisfies a condition. Breadth-first search visits nodes in exactly the order of increasing depth, so the structure of the question matches the structure of the algorithm.

Intuition

Think of ripples spreading from a stone dropped in a pond. The first ring touches everything one step away; the second ring touches everything two steps away. A queue is a line where the first person in is the first person served, and that is exactly what keeps the rings in order: the root enters first, its children enter behind it, and when you serve each child, its own children join the back of the line, behind everyone already there. So all depth-1 nodes are served before any depth-2 node, because every depth-2 node joined the line after every depth-1 node did.

That argument is the whole proof. Claim: the queue only ever contains nodes of two adjacent depths, d and d+1, with all of depth d in front. It holds at the start (just the root), and serving a depth-d node from the front only appends depth-(d+1) nodes at the back, so it holds after every step. Once the last depth-d node has been served, the queue holds exactly the depth-(d+1) nodes, which is why remembering the queue's length at the start of a round marks the level boundary precisely.

The number in a circle is when a queue visits that node. Compare with the depth-first numbering on the previous page: here the numbers rise band by band, and never skip down a level and come back.

Mechanics

The queue loop

Use collections.deque, not a list: list.pop(0) shifts every remaining element and makes the loop quadratic, while deque.popleft() is O(1). Push the root, then repeat: pop from the front, process the node, push its non-empty children at the back. Every node is pushed once and popped once, so the loop does O(n) pushes and pops in total.

Processing a level at a time

Wrap the pop loop in an outer loop over levels. At the top of each round, read size = len(queue) before popping anything and process exactly size nodes. The children pushed during the round are not counted, because size was fixed already. After the inner loop the queue holds the next level, and the outer loop repeats until the queue is empty. Reading len(queue) inside the inner loop's condition is the classic bug: the length grows as you push, so the levels blur together.

Positions, widths and gaps

Some questions care about empty slots. Number the root 0 and give a node at position i children at 2i and 2i+1. This is a heap's array layout with each level shifted to start at 0, and widths only compare positions within a level. The width of a level, counting the empty slots between its leftmost and rightmost nodes, is the last position minus the first position plus one. Python integers do not overflow, so deep skinny trees are safe, but you can subtract the level's first position from each child's position to keep numbers small, which is the habit to keep in languages with fixed-width integers.

Distance in a tree: add parent links

A tree node only points down, so BFS from a node cannot go up. For "all nodes at distance k" first do one pass (any traversal) that records parent[node], then run BFS from the target with a visited set over the three neighbours: left, right and parent. After k rounds the queue holds exactly the answer. The visited set stops the search from walking back along the edge it just came from. You have turned the tree into an undirected graph, which is the doorway to the graph traversal pages.

Queue contents at the start of each round: always one whole level. The amber box is the last node of the round, the one the right-side view keeps. Front of the queue is on the left.

Worked example

The tree is the one from the depth-first page: root 5, children 3 and 8, grandchildren 1, 4 and 9, and one last node 2 hanging off 1.

The level-order result is 5 | 3, 8 | 1, 4, 9 | 2. The right-side view is 5, 8, 9, 2. The zigzag order is 5 | 8, 3 | 1, 4, 9 | 2.

The width column counts empty slots. In round 3 the nodes sit at positions 0, 1 and 3 (node 9 is the right child of 8, which is at position 1), so the level spans 3 − 0 + 1 = 4 slots even though only three nodes are present, and the other levels have widths 1, 2 and 1, so the maximum width is 4.

Implementation

from collections import deque


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


def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):                  # size fixed before the loop starts
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels


def zigzag(root):
    return [level[::-1] if i % 2 else level for i, level in enumerate(level_order(root))]


def right_side_view(root):
    return [level[-1] for level in level_order(root)]


def max_width(root):
    best, queue = 0, deque([(root, 0)] if root else [])
    while queue:
        first = queue[0][1]
        best = max(best, queue[-1][1] - first + 1)
        for _ in range(len(queue)):
            node, pos = queue.popleft()
            pos -= first                             # keep positions small
            if node.left:
                queue.append((node.left, 2 * pos))
            if node.right:
                queue.append((node.right, 2 * pos + 1))
    return best


def min_depth(root):
    queue, depth = deque([root] if root else []), 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if not node.left and not node.right:
                return depth                         # first leaf is the nearest
            queue.extend(child for child in (node.left, node.right) if child)
    return 0


def distance_k(root, target, k):
    parent = {}

    def link(node, up):
        if node:
            parent[node] = up
            link(node.left, node)
            link(node.right, node)

    link(root, None)
    queue, seen = deque([target]), {target}
    for _ in range(k):
        for _ in range(len(queue)):
            node = queue.popleft()
            for nxt in (node.left, node.right, parent[node]):
                if nxt and nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
    return [node.val for node in queue]


def connect_levels(root):
    """Link each node to its right neighbour; assumes nodes have a .next field."""
    queue = deque([root] if root else [])
    while queue:
        prev = None
        for _ in range(len(queue)):
            node = queue.popleft()
            if prev:
                prev.next = node
            prev = node
            queue.extend(child for child in (node.left, node.right) if child)
    return root

max_width reads the front and back of the queue before popping, so the positions it uses belong to the level about to be processed. distance_k returns the queue itself after k rounds; if the tree is smaller than k, the queue empties and the answer is an empty list.

Variations and edge cases

• Depth-first with a depth parameter. Level lists can also be built recursively: if depth == len(levels): levels.append([]), then append to levels[depth]. Visiting right before left makes the first value seen at each depth the right-side view. It needs O(h) stack, and BFS needs O(width).
• Two stacks instead of reversing. Zigzag can alternate between two stacks, but reversing the finished level list is simpler and just as fast.
• Multi-source starts. Put several nodes in the queue before the first round and distances are measured to the nearest of them. Rotting-fruit and nearest-exit style questions use this on grids.
• Serialization. Writing a null marker for each missing child keeps the level array aligned with the queue; trailing nulls can be trimmed.
• Edge cases: an empty tree (guard the root, or the first popleft fails), a single node, a chain (width 1 per level, so the queue stays tiny), a complete tree (the last level holds about half the nodes, so the queue is O(n)), and duplicate values, which is why the parent map is keyed by node object, not by value.

Complexity and tradeoffs

• Time: O(n). Each node is enqueued once and dequeued once. The example processed 7 nodes in 4 rounds.
• Space: O(w), where w is the largest level's size. For a perfect tree that is about n/2, so BFS uses more memory than depth-first search, whose stack is O(height). For a chain the situation reverses: BFS needs O(1) and DFS needs O(n).
• Baseline. Answering "which nodes are at depth d" with a fresh depth-first search for each d costs O(n) per query, O(n·h) for all depths. One BFS gets every level in O(n).
• When it fails. Questions that need information from the whole subtree below a node (height, diameter, path sums) are naturally depth-first with return values. BFS also gives no help for weighted edges: it finds fewest edges, not least total weight, so shortest paths with weights need Dijkstra.

Problems

The home problems are all one loop with a different thing kept per round: the whole level (level order), the level reversed on alternate rounds (zigzag), its last node (right-side view), positions at both ends (maximum width), and a parent map for the distance question. Invert, symmetric tree and serialization have other home pages and appear below as "also uses".

Medium

• 102. Binary Tree Level Order Traversal Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Process the queue one level at a time by first reading its current length, which is exactly the width of that level.
• 103. Binary Tree Zigzag Level Order Traversal Grind 169
  Do an ordinary level-order traversal and reverse every other level before recording it.
• 199. Binary Tree Right Side View Grind 169 NeetCode 150 NeetCode 250
  The last node of each BFS level is the one visible from the right.
• 662. Maximum Width of Binary Tree Grind 169
  Number nodes like an array heap, 2i and 2i+1, and a level's width is its last index minus its first plus one.
• 863. All Nodes Distance K in Binary Tree Grind 169
  Record each node's parent so the tree becomes an undirected graph, then BFS k steps from the target.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 101. Symmetric Tree Easy
• 226. Invert Binary Tree Easy
• 45. Jump Game II Medium
• 297. Serialize and Deserialize Binary Tree Hard

Connections

This page uses the deque from the Python toolkit page and contrasts with depth-first search on trees: the same tree, a different visit order, a different question answered naturally. The queue-with-parent-links trick generalises directly to breadth-first search on graphs and grids, where a visited set replaces the tree's built-in absence of cycles. Serializing a tree level by level is the first half of the tree construction page.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 22.2 (breadth-first search, with the proof that the queue holds vertices at distance d then d+1).
• Sedgewick and Wayne, Algorithms, section 4.1 (breadth-first paths) and the level-order traversal in section 3.2.
• Skiena, The Algorithm Design Manual, the chapter on graph traversal: BFS and shortest paths in unweighted graphs.
• Moore, E. F., "The shortest path through a maze" (1959), the original description of breadth-first search for shortest paths.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.