Breadth-First Search I

Breadth-first search explores a tree level by level using a queue. Nodes come out in order of depth, so every node at depth $d$ is dequeued before any node at depth $d + 1$.

Variant	What each pass does	Typical use
Early exit	Stop at the first match	Minimum depth, shallowest leaf
Level inspection	Check relationships within a depth	Cousins, level averages
Level collection	Emit each depth as its own list	Level-order and zigzag views

The loop is the same every time. Read the queue size, pop that many nodes, and push their children. Everything popped in one round is one level, so you can track depth, compare nodes at a depth, or collect each row. A binary tree has one path to every node, so no visited set is needed until part II.

Approach	Time	Extra space
DFS over the whole tree	$O(n)$	$O(h)$, tree height
BFS over every level	$O(n)$	$O(w)$, widest level
BFS, stop at the first match	Nodes above the match	$O(w)$

Reach for BFS over DFS whenever depth is the question. The shallowest match is the first one dequeued, so you can return right away instead of walking the rest of the tree.

The problems below start with returning at the first leaf dequeued, move to testing whether two nodes are cousins, and end with collecting the tree level by level.