skip to content

A breadth-first walk of a shallow org chart with 100,000 direct reports exhausts memory, but depth-first does not. Why?

level: seniorimportance: should knowfreq 50%

answer

  1. each walk is bounded by a different dimension
  2. one holds a path, one holds a level
  3. how wide is the widest level here
  4. compare O(h) against O(w)
  5. shallow and wide flips the usual advice

basics

~20 s

Breadth-first peak memory is the widest level, depth-first peak memory is the height. A wide, shallow org chart has a frontier of 100,000 nodes but a depth of two or three, so the queue explodes while the recursion barely nests.

solid answer

~50 s

The two walks are bounded by different dimensions of the same structure. A level-by-level walk holds a frontier queue whose peak size is the **widest level**, `O(w)`; a depth-first walk holds one root-to-node path, `O(h)`. An org chart with 100,000 people reporting to one executive has w ≈ 100,000 and h ≈ 3, so the queue holds essentially the whole organisation while the recursion nests three deep. Reverse the shape — a long single-report chain — and it flips exactly: the frontier is one node while the recursion is n frames deep. So "depth-first uses less memory" is not a rule, it is a bet on the data's shape. The second-order point: the frontier lives on the general heap with a large ceiling, whereas frames live in a small fixed stack region, so an equally sized depth problem usually fails sooner and harder.

code

pseudocode · 9 lines
pseudocode
walk_by_level(root):
    q = empty_queue
    enqueue(q, root)
    while not is_empty(q):
        node = dequeue(q)
        visit(node)
        for i in 0..length(node.reports) - 1:
            enqueue(q, node.reports[i])
    return

go deeper

for a junior

Remember the two bounds by name: a level-by-level walk holds the widest level, a depth-first walk holds the current path. Neither is automatically the cheaper one.

for a middle

Explain the frontier: all children of a level are enqueued before the next level is dequeued, so peak queue size is the widest level. Work an example in both directions, wide-and-shallow and deep-and-narrow.

for a senior

Show production judgment — ask what shape the data takes, note that stack and heap ceilings differ by orders of magnitude, and say which counters you would add to turn the argument into a measurement.

for a principal

Own the cross-cutting rule: which of your data shapes are attacker- or user-controlled in width versus depth, and what the default traversal choice and memory budget are for services walking them.

## Two different dimensions, not two different efficiencies The reflex answer — "depth-first uses less memory than breadth-first" — is a half-truth that gets people into production incidents in both directions. The accurate statement is that the two traversals are bounded by two different measurements of the structure: | Walk | Peak extra space | Bounded by | |---|---|---| | Depth-first (recursive) | O(h) frames | height / longest path | | Depth-first (explicit stack) | O(h) entries on the heap | height / longest path | | Breadth-first | O(w) queue entries | widest level (frontier) | For a tree, `w` can be as large as about `n/2` (all leaves on the bottom level of a balanced tree, or all children of the root in a star shape) and as small as 1 (a chain). `h` can be as large as `n` (a chain) and as small as about `log n` (balanced). The two are, roughly speaking, in tension: shapes that make one large make the other small. ## The org chart, both ways **Wide and shallow.** A retail organisation where a single director has 100,000 store staff reporting in, three levels total. A level-by-level walk enqueues all 100,000 subordinates before dequeuing the second one, so the queue holds the whole workforce. A depth-first walk enters an employee, finishes their (empty) subtree, returns, and moves on — three frames live at any moment, no matter how many people exist. Depth-first wins by five orders of magnitude. **Deep and narrow.** A chain of approvers where each person has exactly one report, 100,000 deep. Now a recursive depth-first walk holds 100,000 frames and overflows the stack, while the level-by-level walk's frontier never exceeds a single node. Breadth-first wins by five orders of magnitude. Same two algorithms, opposite verdicts, and nothing distinguishes the cases except the shape of the data. This is why the senior answer to "which traversal is cheaper?" is a question back: *what shape is the input, and is that shape under our control?* ## The asymmetry between the queue and the stack Even when `w` and `h` are similar, the two costs do not fail alike. A frontier queue is ordinary heap memory: the ceiling is large, the entries are typically pointer-sized, and running out surfaces as allocation pressure and, ultimately, a memory error the process can often observe and handle. Recursion frames live in a per-thread stack region that is fixed at thread creation, commonly around a megabyte, and each frame is much larger than a pointer because it holds the call's arguments and locals. The practical consequence is that a depth of 100,000 tends to be fatal while a frontier of 100,000 is often merely expensive — and that on a service with many concurrent workers, the stack cost is reserved per thread and multiplies by concurrency while the heap is shared. So three quantities decide the choice, not one: the shape of the data, the ceiling each region has, and how many workers pay the cost at once. ## Choosing deliberately - **Depth known small, width possibly huge** (org charts, file trees with big directories, one-hop-heavy graphs): prefer depth-first. - **Width known small, depth possibly huge** (reply chains, linked histories, dependency chains): prefer level-by-level, or a depth-first walk whose pending work sits on the heap rather than the call stack, which keeps the traversal order but moves the O(h) cost to the roomier region. - **Neither bounded**: pick by which failure you can tolerate and instrument the peak. Log the maximum frontier size and the maximum depth reached on real traffic; both are cheap counters and both turn an argument into a measurement. - **You need shortest-hop distances anyway**: then the level-by-level order is a correctness requirement, and the frontier cost is the price of the answer, not a free choice. ## The claim, stated precisely Neither traversal is cheaper in general. Depth-first costs O(h), breadth-first costs O(w), and for any given structure one of those is small and the other may be enormous. Picking a traversal without knowing which dimension of your data is unbounded is guessing, and the guess is graded by production.

  • Why can a queue holding 100,000 nodes survive where 100,000 stack frames would crash?
    The queue lives in the general heap, where the ceiling is large and each entry is roughly pointer-sized. Frames live in a per-thread stack region fixed at thread creation, commonly around a megabyte, and each frame carries the call's arguments and locals. The stack ceiling is reached far sooner, and crossing it kills the thread outright rather than raising memory pressure.
  • Which walk would you choose for a deep, narrow reply chain of unknown length?
    Either a level-by-level walk, whose frontier stays at one or two nodes on a chain, or a depth-first walk that keeps its pending work in a heap-allocated stack instead of the call stack. Both keep the O(depth) cost off the fixed stack region. Choose between them by whether the visit order matters to the result.
  • How would you decide when neither the width nor the depth of the input is bounded?
    Measure before choosing. Instrument the maximum frontier size and the maximum depth reached on real traffic — two counters — and let the distribution decide. Meanwhile pick the walk whose failure you can survive: a large frontier usually degrades and can be caught, whereas a deep recursion kills the worker immediately.

Depth-first carries one branch of a family tree at a time; breadth-first must hold an entire generation before it can move on to the next.

saying these in an interview costs you the question

  • States that depth-first always uses less memory than breadth-first
  • Compares the two on time complexity only, both O(n)
  • Thinks a wide tree makes the recursion deeper
  • Ignores that stack and heap have very different ceilings
  • Picks a traversal without asking about the data's shape

context

resolving links…