In a queue-based level-order walk of a binary tree, how do you know where each level ends?

## The problem Drive a walk with a first-in-first-out queue — enqueue the root, then repeatedly dequeue a node, emit it, and enqueue its children — and the nodes do come out in tier order: root, then everything at depth 1, then everything at depth 2. That much is free. What is *not* free is the boundary. The output is one flat stream, and an operations dashboard that wants to render a routing rule set as one row per tier needs to know where each row stops. ## The invariant that solves it The queue is first-in-first-out and children are always enqueued *behind* everything currently waiting. So if, at some moment, the queue holds exactly the nodes of level d and nothing else, then consuming all of them — enqueueing each one's children as you go — leaves the queue holding exactly the nodes of level d+1 and nothing else. That is an inductive invariant, and it seeds correctly: after enqueueing the root, the queue holds exactly level 0. The only thing you must do to exploit it is record how many nodes level d has **before** you start consuming, because the queue's size changes as you go: ``` enqueue(Q, root) while not empty(Q): k = size(Q) // exactly this level's nodes level = empty list for i in 0..k-1: node = dequeue(Q) add(level, node.value) if node.left != nil: enqueue(Q, node.left) if node.right != nil: enqueue(Q, node.right) emit(level) ``` The most common bug in this shape is re-reading `size(Q)` inside the inner loop, or writing `while i < size(Q)`. By then the queue is already growing with the *next* level's nodes, so the loop runs past the boundary and merges tiers — and it merges them differently depending on the tree's shape, which makes the bug look intermittent. ## Alternatives, and what they cost **Sentinel marker.** Enqueue a marker token after the root; each time the marker is dequeued, the current level has ended — emit the row, and if the queue is not empty, enqueue the marker again for the next tier. Equivalent, one extra token, and it needs a guard so an empty queue does not re-enqueue the marker forever. **Depth-tagged entries.** Enqueue pairs of (node, depth) and start a new row whenever the depth changes. Correct, costs an extra field per queued entry, and reads well when the depth is wanted in the output anyway. **Recursion with buckets.** Level-order output does not strictly require a queue. Walk depth-first, pass each node's depth down, and append each value into the bucket for its depth; read the buckets out in order at the end. The tiers come out right — but note the route is nothing like level-order, so the memory profile is the buckets plus the descent, and the output only exists once the whole walk has finished. The queue version can stream a tier the moment it is complete. ## Cost Time is O(n): each node is enqueued once and dequeued once, and the inner loop's iterations across all rounds sum to n. The queue holds at most one level at a time plus the children being appended, so its peak is on the order of the tree's widest level — for a perfect tree that is the last level, roughly n/2 nodes, so the queue's peak is linear in n for wide trees and small for narrow ones. ## Why no visited set is needed A candidate who has drilled graph traversal often reaches for a visited set out of habit. A binary tree does not need one: every node has exactly one parent and there are no cycles, so a node can be reached only through its parent and is enqueued exactly once. The visited set exists to handle the two things trees rule out — multiple paths to the same node, and cycles. ## Failure modes to name - Re-reading the queue size inside the inner loop, merging adjacent tiers. - Enqueueing empty children and then emitting them as if they were nodes; guard each child, or accept the placeholders deliberately if the dashboard wants a shape-preserving grid. - Using a last-in-first-out stack instead of a queue and expecting tiers — that produces a depth-first order, not a level order. - Assuming the queue stays small; on a wide tree it holds a whole tier. - Handling the empty tree by dereferencing the root before the loop; the guard belongs before the first enqueue.