A tree-diameter function calls a separate height routine at every node — what is its true time complexity?
answer
- one walk called from inside another walk
- how many times is one node's height computed?
- count once per ancestor
- sum of all node depths
- a chain makes that sum quadratic
basics
~20 sWorst case O(n^2): each node's height is recomputed once per ancestor, so a chain-shaped tree pays the sum of all depths. A balanced tree costs O(n log n). Fusing both walks into one post-order pass restores O(n).
solid answer
~40 sThe code is correct and quadratic in the worst case. At each node it calls a height routine that walks that node's whole subtree, so a node at depth `d` has its height recomputed `d + 1` times. Total work is the sum of all node depths: on a degenerate chain that is `n(n-1)/2`, i.e. `Theta(n^2)`; on a balanced tree the recurrence `T(n) = 2T(n/2) + O(n)` gives `Theta(n log n)`. Mind the direction — `O(n^2)` describes the worst shape, not every input. The fix is fusion rather than memoization: one post-order pass returning each node's height while recording `height(left) + height(right) + 2` into a running maximum, `O(n)` time and `O(h)` stack. Review heuristic: a helper that walks a subtree, called from inside a walk of that same subtree, is a nested traversal.
code
pseudocode · 8 linesheight(v):
if v == null: return -1
return 1 + max(height(v.left), height(v.right))
diameter(v):
if v == null: return 0
through_v = height(v.left) + height(v.right) + 2
return max(through_v, diameter(v.left), diameter(v.right))go deeper
Recognize that calling a routine which walks a subtree from inside another walk of the same subtree repeats work. Being able to say "each node's height is computed many times" is enough here.
Derive the total as the sum of node depths and show both bracketing shapes: quadratic on a chain, n log n when balanced. Then describe the fused single pass that returns height and records the candidate.
Catch it in review and write a comment that names the triggering input shape, not just the exponent. Say how you would prove it in production — a growth test on a skewed input rather than a correctness assertion.
Decide how this class of defect stops reaching production at all: which reviews get a cost lens, whether performance-shaped tests exist for hot paths, and when a cache is an acceptable retrofit versus a new invalidation burden nobody owns.
## The diff A change lands that computes the longest node-to-node path (the diameter) of a tree-shaped network topology, and it looks reasonable: one routine computes a height, another computes the diameter by combining heights. Both are individually correct, the tests pass, and the reviewer's instinct says approve. The defect is not correctness — it is that the two recursions are nested, and the cost of the outer one multiplies the cost of the inner one. ## Counting the work exactly Let `size(v)` be the number of nodes in `v`'s subtree. A call to the height routine on `v` visits every node of that subtree, so it costs `Theta(size(v))`. The diameter recursion calls it once at every node. Total work is therefore proportional to the sum of `size(v)` over all `v`, which — by counting from the other side — equals the sum over all nodes of that node's depth plus one, since a node is inside the subtree of exactly its ancestors and itself. Two shapes bracket the behaviour: - **Degenerate chain** (each node has one child): depths are `0, 1, 2, ..., n-1`, summing to `n(n-1)/2`. That is `Theta(n^2)`. - **Perfectly balanced**: the recurrence is `T(n) = 2T(n/2) + Theta(n)` — the `Theta(n)` being the height walk at the current node — giving `Theta(n log n)`. So the honest sentence in the review is: "worst case `O(n^2)`, triggered by deep skewed trees; roughly `n log n` when the tree is balanced". Saying only `O(n^2)` invites the reply "but our trees are balanced", and saying only `O(n log n)` hides the failure mode. Big-O is an upper bound; naming the *shape* that reaches it is what makes the review actionable. ## Why the tests were green Because the output is right. Only the cost is wrong, and cost is invisible at the sizes unit tests use — at `n = 20`, `n^2` and `n` differ by a factor no assertion is watching. This class of defect survives every correctness gate and surfaces later as a latency regression on a real-shaped input: a topology where one uplink chain runs deep, a history that grew by appending, any tree built from data that arrives in order. The two ways to catch it are reading for the nested walk, and a growth test that runs the routine on a deliberately skewed input an order of magnitude larger and checks that time scales roughly linearly. ## The fix Do not add a cache first. The two computations want the same post-order traversal, so fuse them: one recursion returns the node's height to its parent, and on the way it records `height(left) + height(right) + 2` — the best path topping out at this node — into a running maximum held outside the recursion. Every node is visited once, constant work each, `O(n)` time and `O(h)` stack space. Memoizing height is a legitimate second-best: caching each node's height turns every repeat into a constant-time lookup and also restores `O(n)`, at the price of `O(n)` memory and a cache whose invalidation is now your problem if the tree can change. It is the right tool when the two computations genuinely must stay separate — different owners, different call sites — and the wrong tool when one traversal already does both. ## The generalizable smell The reviewer's rule that catches this family in seconds: **a helper that itself walks a structure, invoked from inside a walk of the same structure, is a nested traversal until proven otherwise.** It shows up as a length or size call inside a loop over the same collection, a subtree aggregate recomputed at every level, a re-scan to answer a question the outer pass already had the data for. The multiplication is rarely visible in the diff's line count — the quadratic here is nine lines long — so the check has to be structural rather than visual. ## What to say in the review Name the cost, the input shape that reaches it, and the concrete fix, in that order. "This recomputes each node's height once per ancestor, so it is `O(n^2)` on a deep chain and `O(n log n)` when balanced; returning height from the same post-order pass that records the best candidate makes it `O(n)` with no cache." That is a comment the author can act on immediately, and it teaches the pattern rather than just flagging the instance.
- Why do unit tests on small trees never catch this?Because the output is correct — only the cost is wrong, and at the sizes tests use, the difference is invisible. Catching it needs either structural reading (a subtree walk inside a subtree walk) or a growth test on a deliberately deep, skewed input that asserts time scales roughly linearly rather than asserting a value.
- Would memoizing the height routine fix it?Yes, and it restores `O(n)` time at `O(n)` memory, since each repeated call becomes a lookup. But it is the retrofit for when the two computations must stay separate. If one traversal can produce both values, fusing them gets the same bound with no cache and no invalidation question when the tree changes.
- How would you phrase the cost in the review comment so it is actionable?Name the worst case, the shape that triggers it, and the fix together: quadratic on a deep chain, about `n log n` when balanced, fixed by returning height from the same post-order pass that records the candidate. A bare "this is `O(n^2)`" gets answered with "our trees are balanced" and the thread stalls.
saying these in an interview costs you the question
- Calls the nested version O(n) because it is a single recursion
- Blames recursion overhead instead of the repeated subtree walk
- Claims quadratic behaviour on every input shape
- Assumes a memo is required when one pass already suffices
- Treats green unit tests as evidence the cost is fine