Level-order over an n-ary org chart: how do you know where one tier ends?

## Why the boundary needs bookkeeping A level-order walk keeps a queue, pops a node, enqueues that node's children, and repeats until the queue is empty. That produces the right *sequence* of nodes — every node at depth `d` before any node at depth `d + 1` — but it produces a flat stream, and rendering an org chart tier by tier needs the stream cut into groups. The naive instinct, "the queue empties between levels", is wrong: at the moment you pop the last node of a tier, that tier's earlier nodes have already enqueued their reports, so the queue is full of the *next* tier. The queue is empty exactly once, at the very end. ## The size-snapshot technique The invariant that makes it work: **at the top of each round, the queue contains exactly the nodes of one tier, in order.** Establish it by seeding the queue with the root alone. Maintain it like this: 1. Let `size = length(queue)` — read once, before popping anything. 2. Repeat `size` times: pop a node, emit it into the current tier's output, and enqueue every entry of its children list in order. 3. Nothing popped in this round was enqueued in this round, because you fixed `size` up front. So after the round the queue contains exactly the children of the whole tier — the next tier, in order. 4. Stop when the queue is empty. The single most common bug is reading the queue's length *inside* the loop instead of before it: the bound then grows as children are added, and the round swallows part of the next tier. A second common bug is enqueuing only the first child, which comes from binary habits and quietly drops most of the chart. ## The representation point This leaf's real lesson hides in step 2: "enqueue every entry of its children list". If the node type declares two fixed slots, that sentence has no meaning — a manager with five direct reports cannot be represented at all, let alone traversed. Hierarchies people actually render (reporting lines, directory listings, document element trees, category menus) have unbounded fanout, so the node carries an ordered collection of children and the traversal loops over it. The binary shape is not a simplification of these models; it is a different model that cannot express them. When an interviewer hands you a node type with `left` and `right` and asks you to render an org chart, the first correct move is to change the node type. Order matters too. The children list is ordered, and that order is usually the display order. Level-order preserves it as long as each node enqueues its children front to back — a queue is first-in-first-out, so enqueue order is emit order within the next tier. ## Alternatives to the count - **Depth-tagged entries.** Enqueue `(node, depth)` pairs, or store a depth field when enqueuing. Start a new tier whenever the popped depth differs from the previous one. This costs a little extra memory per queued entry but hands you the tier number directly, which is convenient when the renderer needs indentation levels. - **Sentinel markers.** Push a marker after the root, and each time you pop the marker, close the current tier and push a new marker if the queue is non-empty. Compact, but easy to get wrong at the end, where pushing a final marker into an empty queue loops forever. - **Two lists instead of a queue.** Keep the current tier as a list, build the next tier by walking it and collecting all children, then swap. This is often the clearest version when the output *is* tiers, and it makes the invariant self-evident because each list literally is a tier. It also parallelises naturally, since the nodes of one tier are independent. All four are O(n) time. Memory differs only in constants; the dominant term in every version is the widest tier, because at the boundary you are holding a full tier of node references. ## Cost, honestly stated Time is O(n): each node is enqueued once and popped once, and the enqueue loops run once per child link, `n - 1` in total. Peak auxiliary memory is proportional to the maximum tier width. That is the interesting asymmetry with depth-first walks: a wide, shallow chart is cheap to recurse over and expensive to hold a tier of, while a deep, narrow chain is the reverse. For an org chart — typically shallow and very wide at the middle tiers — the widest tier is the number that matters, and it is worth saying out loud that rendering a hundred-thousand-person chart tier by tier means materialising the widest tier in memory at once, which is an argument for streaming a tier out as it is drained rather than collecting all tiers first. ## What a strong answer sounds like Name the invariant ("the queue holds exactly one tier at the top of each round"), give the snapshot mechanic, mention the read-size-inside-the-loop bug, note that the node needs a children list for any of it to work, and close with O(n) time and widest-tier memory.