Why does level-order traversal of a company org chart use a queue instead of a stack?
answer
- Both traversals share one skeleton
- Only the removal discipline differs
- Ask what the pending container holds
- Discovered earlier means same depth or shallower
- First-in-first-out preserves discovery order
basics
~20 sA queue hands nodes back in the order they were discovered, so every person at one depth is expanded before anyone a depth lower. A stack returns the most recent discovery first, which dives down a single reporting chain instead.
solid answer
~40 sLevel-order traversal means visiting the chief executive, then all direct reports, then all of their reports, and so on. The traversal keeps a container of discovered-but-not-yet-expanded people; the container's removal order *is* the visit order. A queue is first-in-first-out, so a person discovered earlier — necessarily at the same depth or shallower — comes out earlier, and the frontier drains one whole level before the next level starts. A stack is last-in-first-out: the child you just discovered comes out before the siblings discovered a moment earlier, so you walk one reporting chain to the bottom and back up. Same traversal skeleton, same visited nodes, completely different order — the only thing that changed is the removal discipline of the pending set.
go deeper
Be ready to say, in one sentence, that first-in-first-out returns nodes in discovery order and that discovery order rises level by level. Then say what a stack would do instead and name the resulting traversal.
Explain the invariant: the pending container holds at most two adjacent depths, and the last node of one depth leaving means the container now holds exactly the next depth. Interviewers use that invariant as the setup for level grouping.
Show that peak memory depends on the data's shape — widest level for the queue, height for the stack — and pick the traversal accordingly rather than by habit. Say which questions the ordering answers for free.
Own the framing that the removal discipline is the algorithm's contract. When someone swaps the container 'for efficiency', the ordering guarantee downstream code relies on quietly disappears, and that is a design conversation, not a micro-optimisation.
## The skeleton both traversals share Traversing a hierarchy is always the same three-line idea: put the root into a container of *pending* items; repeatedly remove one, report it, and insert its children; stop when the container is empty. Nothing in that skeleton says which pending item comes out next. That single decision — the removal discipline of the container — is what separates breadth-first (level-order) from depth-first. Take an org chart: a chief executive at depth 0, four vice presidents at depth 1, their directors at depth 2, and so on. Because a reporting hierarchy is a tree, every person is reached from exactly one parent, so the traversal needs no extra bookkeeping to avoid revisits — the container alone determines the order. ## Why first-in-first-out gives you levels A queue removes the item that has waited longest. Two facts follow, and together they are the whole proof: 1. **Discovery order is non-decreasing in depth.** A node at depth `d+1` is only ever inserted while expanding a node at depth `d`. So the first time anything at depth `d+1` enters the queue, every node at depth `d` is already in it (or already processed). 2. **First-in-first-out preserves that order on the way out.** Nothing overtakes anything, so removal order equals insertion order equals discovery order. The consequence is the invariant worth being able to state out loud: *at any moment the queue holds only nodes of two adjacent depths* — the tail of the current level and the head of the next. When the last depth-`d` node leaves, the queue contains exactly the depth-`d+1` nodes, in left-to-right order. That is why level-order traversal and the queue-based frontier are the same thing described from two sides. ## Why last-in-first-out does not Swap in a stack and the second fact breaks: the newest discovery jumps ahead of everything queued before it. Expand the chief executive, push four vice presidents, pop the last one, push its directors, pop the newest director… you have walked to the bottom of one branch before the other three vice presidents were ever touched. That is depth-first order. It is a perfectly good traversal — it just answers different questions. A common half-right answer is *"a stack gives you the same levels, only reversed."* It does not. Reversal would still keep depth-1 people adjacent to each other; a stack interleaves depths freely — after a few steps the pending set spans the entire height of the chart, not two adjacent levels. ## What the ordering buys you Because a queue-driven traversal finishes depth `d` before starting depth `d+1`, the first time you encounter a person is via a shortest chain of reporting links from the root. Anything of the form *"how many management layers separate these two roles"*, *"who is within two hops of this executive"*, or *"expand the org chart one layer at a time in the UI"* falls out of the order for free. A depth-first walk reaches the same people but can reach them first by a long, winding path, so it needs extra machinery to answer the same questions. The converse also matters: depth-first is the right tool when the answer lives at the bottom (does any chain from here end in an unfilled role?) or when the natural state is a path (the chain of managers above the current person), because a stack *is* that path. ## Cost Both traversals touch every person once and every reporting edge once, so both are linear in the size of the chart. They differ in peak auxiliary space, and the difference is shape-dependent, not universal: the queue holds a whole level at once, so its peak is the widest level — for a broad, shallow chart with thousands of individual contributors at the bottom, that is nearly the whole organisation. A depth-first walk holds one root-to-node chain, so its peak is the height — tiny for a wide chart, but large for a deep, thin one. Neither is the cheaper choice in general; the shape of the data decides. ## The one-sentence version The queue is not decoration around the traversal — it *is* the traversal's ordering guarantee. Change the removal discipline and you have changed which algorithm you are running, even though not a single other line moved.
- At the moment you remove a node during level-order traversal, what depths can the queue contain?At most two adjacent depths. Everything still queued was discovered while expanding the current level or the one before it, so the queue holds the unprocessed tail of the current depth followed by the already-discovered part of the next. It never spans three levels, which is exactly what makes a level-boundary marker cheap to compute.
- Which uses less auxiliary space on a wide, shallow org chart: the queue-based traversal or the stack-based one?The stack-based one. The queue's peak is the widest level, which on a broad chart is most of the organisation at once; the stack's peak is the height of the chart, which is small when the hierarchy is shallow. On a deep, thin chart the comparison flips. Peak space follows the shape of the data, not the choice of algorithm.
- Does the queue-based traversal still visit every node if you start from someone in the middle of the chart?It visits everyone reachable by following reporting links downward from that person — their subtree — and nobody above or sideways. Traversal order is determined by the container, but reachability is determined by which edges you follow from the chosen start.
A queue is the line at a service desk and a stack is a pile of paperwork: the line serves whoever arrived first, the pile serves whatever landed last.
saying these in an interview costs you the question
- Says a stack gives the same levels, just reversed
- Claims the container choice does not affect visit order
- Thinks the queue holds every node visited so far
- Assumes level-order always uses less memory than depth-first
- Cannot say what the pending container holds mid-traversal