Initialize queue with root. While nonempty, set level_size=len(queue), pop exactly that many nodes and append their children. This batch has one depth; increment depth after the batch.
Recognition signals
Output is grouped by depth.
Each layer needs a sum, maximum, last visible node, or zigzag presentation.
The first shallow node satisfying a condition is the answer.
Parents generate exactly the next layer's children.
An iterative traversal avoids dangerous recursion depth.
False friends
Signal
Why it is different
Aggregating subtrees into parents
Height, balance, and diameter are postorder summaries, not naturally layer-based.
Weighted shortest distance
FIFO orders edge count only; unequal nonnegative costs need Dijkstra.
A general graph without deduplication
Trees have unique parents; graph BFS needs visited when enqueuing.
Core invariant
At each round start, the queue contains every node of the current depth and no other depth. After exactly level_size pops, it contains exactly the next depth.
State, transition, and processing order
Item
Definition
State
A FIFO queue, current depth, and a temporary accumulator for the layer.
Transition
Pop one current-level node, update the layer summary, and enqueue each non-null child in stable order.
Frontier / order
Unprocessed current-level nodes followed by already discovered next-level nodes; the frozen size marks their boundary.
Python skeleton
from collections import deque
def levels(root):
if root is None: return []
queue, out = deque([root]), []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
out.append(level)
return out
Correctness sketch
Initially the queue contains only the depth-zero root.
A round removes only the frozen level_size nodes, which share one depth by the invariant.
Their non-null children are exactly the next depth and each has one parent, restoring the invariant after the batch.
Complexity
Time
Space
Parameters
O(n)
O(w), where w is maximum layer width
n is node count and w the largest number at one depth.
Edge cases
empty tree
single node
an extremely wide layer
minimum-depth exit only at a true leaf
zigzag presentation without changing enqueue order
n-ary child ordering
Error patterns
Pattern
Why it fails / fix
Letting the loop length grow dynamically
Freeze the queue size at round start or newly added next-level nodes leak into the current batch.
Returning minimum depth at one missing child
A leaf has no children at all, not merely one absent side.
Reversing enqueue order for zigzag
That can alter future layer structure; reverse presentation or write into a deque instead.
Using list.pop(0)
Removing the list head is O(n) in Python; use deque.popleft().
Selection and exclusion rules
Prioritize level order for ‘per layer,’ ‘shallowest,’ or side-view language.
Capture level_size before the inner loop.
Test early-exit conditions after popping a node whose level is finalized.