In level-order traversal, why snapshot the queue's size before processing each level?

## The invariant the trick rests on Queue-driven level-order traversal has one invariant: **at the top of each outer iteration, the queue contains exactly the nodes of one depth, in left-to-right order.** Everything about level grouping follows from it. If the queue holds exactly the current level, then its size *is* that level's width, and removing that many nodes consumes exactly the level — while the children inserted during those removals accumulate behind them and re-establish the invariant for the next round. ``` enqueue(q, root) depth = 0 while not empty(q) n = size(q) for i in 0..n-1 node = dequeue(q) report(node, depth) for each child in children(node) enqueue(q, child) depth = depth + 1 ``` The entire mechanism is line 4. `n` is read once, before any insertion, and the inner loop is bounded by that frozen number rather than by the live size. ## What breaks without the snapshot Write the inner loop as `while not empty(q)` or `for i in 0..size(q)-1` re-evaluated each step, and the bound chases the insertions. Each node removed adds its children, so the loop keeps finding work and drains the entire structure in a single pass. The nodes still come out in correct level-order sequence — the queue guarantees that regardless — but every level boundary is gone, so you cannot report per-level groups, per-level aggregates, or the depth at which something was found. The failure is silent: the output looks right until someone asks which level a node came from. ## The wrong answer worth naming The most common substitute offered is *"a depth-first walk carrying a depth counter produces the same thing — bucket the nodes by depth as you go."* It half works, and the half that fails is the interesting half. Depth-first reaches every node and labels each with a correct depth, so bucketing by depth does yield the right *set* per level. But within a level the arrival order is the order the branches happened to be explored, not the left-to-right order of the hierarchy: a director under the first vice president and a director under the last vice president land in the same bucket, in an order determined by the recursion, not by position. If the answer must be *"level 2, left to right"* — rendering an org chart row by row, or comparing two hierarchies level by level — the depth-first bucketing is wrong in exactly the way that is hardest to notice on a small hand-drawn example. The queue's arrival order *is* the left-to-right order; that is what you are paying for. A second, subtler cost: depth-first must finish the whole structure before any level is complete, because a late branch can still contribute to level 1. The snapshot version emits each level the moment it is done, which is what makes it usable for incremental rendering or for stopping early at a depth limit. ## The alternatives, and when they win - **Per-node depth tags.** Insert `(node, depth)` pairs and start a new group whenever the depth changes. Correct, and it survives being interleaved with other work, but it carries an extra field through every insertion and removal. - **Level sentinel.** Insert a marker after the root and re-insert it each time it comes out, while the queue is non-empty. Correct, and it reads nicely, but it puts a non-node value into a container of nodes and needs a careful guard so that the final sentinel does not loop forever on an empty queue. - **Size snapshot.** One integer, no extra per-node state, no special values in the container. This is why it is the default in interviews, and why the interviewer usually asks *why it works* rather than *what it does*. The snapshot's one real constraint is that the loop must own the queue for the duration of the level: if anything else inserts into the same queue between the read of `n` and the end of the inner loop, the frozen count no longer matches the level. In a single traversal that is trivially satisfied, and it is the reason the trick is stated as an invariant rather than as a recipe. ## Cost Every node is inserted once and removed once, and each removal does work proportional to that node's children, so time stays linear in the size of the structure. The snapshot adds one integer read per level — asymptotically free. Peak space is still the widest level, unchanged by the trick, which is worth saying out loud because candidates sometimes claim the snapshot reduces memory. It does not; it only recovers information about boundaries that the plain traversal throws away.