What is the stack space of a recursive walk over a tree of n nodes, and what input maximizes it?
answer
- which calls are still open right now
- trace the path from root to current node
- not every node — only one path
- call the path length h
- balanced gives log n, a chain gives n
basics
~10 sO(h), where h is the tree's height: only the current root-to-node path is in progress at once. A height-balanced tree gives O(log n); a degenerate tree that is one long chain gives O(n).
solid answer
~40 sThe bound is `O(h)`, the height, not `O(n)`. A depth-first recursion has exactly the nodes on the current root-to-node path in progress simultaneously — every sibling subtree it already finished has released its frames. So the honest answer is O(h), and h is where the whole conversation lives: a height-balanced tree of n nodes has h ≈ log2 n, giving O(log n), which for a million nodes is about 20 frames. A degenerate tree in which every node has one child has h = n, and the same code now holds n frames. Nothing in the traversal changed; the input's shape did. Answering "O(log n)" flat is the classic mistake, because it silently assumes balance the problem never promised. Say O(h) and then give both endpoints.
go deeper
Recall that a recursive tree walk holds only the current root-to-node path, so the cost is O(height). Know the two endpoints: about log n frames when balanced, n frames when the tree is one long chain.
Explain why finished sibling subtrees cost nothing and derive O(h) from that. Be ready to name the exact input shape that turns O(log n) into O(n) and to estimate real frame counts for a million nodes.
Show you treat h as untrusted data: state the bound, name the degenerate shape, and say what you would do about it when the structure comes from outside your system rather than from a balanced index you maintain.
Frame it as a contract question — which structures in your system carry a proven height bound, which do not, and what the review rule is for recursive code that walks the ones that do not.
## Why the bound is the height A recursive tree walk goes down before it goes across. It enters a node, descends into a child, and that child's whole subtree finishes before the next child is entered. So at any instant the set of calls in progress is exactly the path from the root to the node currently being visited — nothing more. The frames of every subtree already completed were released when those calls returned. That path has length at most `h`, the height of the tree, so the stack cost is `O(h)` frames. It is worth internalising that this is *substantially* less than `O(n)` for a well-shaped tree and *exactly* `O(n)` for a badly-shaped one, and the algorithm cannot tell you which you will get. Only the data can. ## The two endpoints **Height-balanced.** If every node's subtrees differ in height by a bounded amount, the height is `Θ(log n)`. A million nodes means roughly twenty live frames — utterly negligible, which is why people stop worrying and start saying "recursion on a tree is O(log n) space". **Degenerate.** If every node has exactly one child, the tree is a chain: `h = n`. A recursive walk over a hundred thousand such nodes needs a hundred thousand simultaneous frames, which is beyond the fixed stack region a thread is usually given, and the program crashes. This is not a contrived shape. Nested discussion threads where each message replies to the last, directory hierarchies generated by a script, and linked structures modelled as degenerate trees all produce it, and they produce it from *user* data rather than from anything the author chose. **In between.** For an arbitrary tree of n nodes the height satisfies `⌈log2(n+1)⌉ ≤ h ≤ n` for binary trees. Both ends are achievable, so O(h) is the only claim that is true without extra assumptions. ## The interview move When you are asked for a traversal's space complexity, the answer that scores is three beats long: 1. "O(h) for the recursion stack, plus whatever the traversal itself allocates." 2. "If the tree is balanced, that's O(log n)." 3. "If it's skewed into a chain, that's O(n) — and that's the input I'd worry about." Beat three is the one candidates skip, and it is the one that signals you have shipped this. "What input breaks this?" is the interviewer's next sentence anyway; get there first. ## Bounding the depth on purpose When an algorithm recurses on two parts of different sizes, you can often bound the depth even without a balance guarantee. A divide-and-conquer routine that **recurses into the smaller part and loops on the larger** has a depth of at most `log2 n`, because each nested call handles at most half of what its caller had. This is a genuine space guarantee rather than an average-case hope, and it is why careful implementations of partition-based algorithms bound their stack even on adversarial input. If your recursion always recurses into both parts, no such bound exists and the worst case is the full depth. ## Related shapes, so the bound does not surprise you - **Many-way trees.** For a tree where nodes may have any number of children, the same reasoning holds unchanged: depth-first recursion is O(h), where h is the longest root-to-leaf path. Fan-out is irrelevant to the stack; it is relevant to a breadth-first frontier. - **Graph depth-first search.** On a graph with V vertices, the recursion depth is bounded by the longest simple path explored, which is `O(V)` in the worst case — a graph is a chain more easily than a tree is. - **Total space.** The stack is only one term. Add anything the traversal accumulates. State the sum, not the largest half you noticed first. ## The direction of the claim O(h) is an upper bound on the stack cost, and h is a property of the input, not of your code. Saying "O(log n)" is a claim about the data, and unless the structure carries a balance guarantee, it is a claim you are not entitled to make. Conversely, "O(n) worst case" does not mean the code is bad — it means the depth is untrusted, and either you bound the depth, verify balance, or move the frames somewhere with a higher ceiling.
- How would you phrase this bound in an interview when the tree's balance is not guaranteed?Say O(h) first, then give both endpoints: O(log n) if the tree is height-balanced, O(n) if it degenerates into a chain. Naming the worst-case input as part of the answer is what separates a memorised complexity from an understood one, and it pre-empts the interviewer's inevitable follow-up about what breaks it.
- Can a divide-and-conquer recursion guarantee O(log n) depth without a balance guarantee?Yes, if it recurses into the smaller part and loops on the larger one. Each nested call then handles at most half of what its caller had, so the depth cannot exceed log2 n. If instead it recurses into both parts, the depth follows whichever part is deepest and the worst case is the full size.
- Does the number of children per node change the stack bound?No. Depth-first recursion holds one root-to-node path regardless of fan-out, so the bound stays O(h). Fan-out changes how many siblings wait to be entered, but a waiting sibling has not been called yet and reserves nothing. Wide-and-shallow shapes are cheap for a recursive walk and expensive for a level-by-level one.
saying these in an interview costs you the question
- Says O(log n) without checking the tree is balanced
- Says O(n) because there are n nodes to visit
- Assumes every tree in production is roughly balanced
- Thinks high fan-out increases recursion depth
- Confuses 'balanced' with 'sorted' or 'complete'