skip to content

When is a rerooting tree DP worth its complexity over simply running one traversal per candidate root?

level: principalimportance: nice to knowfreq 20%

answer

  1. how often does the whole answer change?
  2. one traversal per candidate versus two total
  3. what changes when the root shifts one edge?
  4. subtree size decides the adjustment
  5. quadratic versus linear, at which measured n?

basics

~20 s

Rerooting answers every node in two linear passes instead of one traversal per node, turning quadratic work into linear. Take it when the measured input size and recompute frequency actually miss the latency budget; below a few thousand nodes the simpler per-root loop usually wins and is far easier to keep correct.

solid answer

~50 s

Say you must pick the closet that minimises total hop-distance to every office on a link tree. The obvious version runs one traversal per candidate and is `O(n^2)`. Rerooting does a downward pass computing each subtree's size and internal distance sum, then an upward pass that transfers a parent's total to a child in `O(1)`: moving the root across one edge brings the child's whole subtree one hop closer and pushes everything else one hop farther, so `f(child) = f(parent) + n - 2 * size(child)`. That is `O(n)` overall. The decision is not asymptotic, it is economic: measure `n`, the recompute frequency and the budget. At a few thousand nodes recomputed nightly, keep the naive loop — and keep it forever as the test oracle. When the tree grows or the answer is recomputed per request, take the rewrite, but land it with property tests against the naive version and a named owner, because an inverted aggregate is a subtle thing to maintain.

go deeper

for a junior

Know that a tree DP's answer usually depends on which node you treat as the root, and that getting every node's answer naively costs one full traversal per root.

for a middle

Explain the two-pass structure: a downward pass computing subtree aggregates, then an upward pass that converts a parent's answer into a child's in constant time.

for a senior

Derive the one-edge shift for a concrete objective, name the invertibility requirement that makes it possible, and say how you would test the fast version against the naive one before trusting it.

for a principal

Frame it as a cost decision with numbers: the measured input size and its growth, the recompute frequency, the latency headroom, and whether the team can maintain an inverted-aggregate technique long after you wrote it.

## The problem shape Standard tree DP answers one question: what is the value **at the root**. Plenty of real questions instead ask for the value at *every* node — which site minimises total distance to all others, what does each node's aggregate look like if the tree hung from it. The naive answer is a loop: root at each node in turn, run the linear DP, keep the results. That is `n` traversals of `n` nodes, `O(n^2)`. Rerooting removes the outer loop. It is two passes: 1. **Downward (post-order).** With an arbitrary fixed root, compute for every node the aggregates over its own subtree — for a total-distance objective, `size(v)` (nodes in the subtree) and `down(v)` (sum of distances from `v` to everything in its subtree). 2. **Upward (pre-order).** Carry the *complete* answer from a parent to a child using only `O(1)` arithmetic, since the child's answer is the parent's answer adjusted for the one edge that moved. For total distance on unweighted links, that adjustment is exact and easy to justify: moving the root from `u` to its child `v` brings every one of the `size(v)` nodes in `v`'s subtree one hop closer, and pushes the other `n - size(v)` nodes one hop farther. So `f(v) = f(u) - size(v) + (n - size(v)) = f(u) + n - 2 * size(v)` One subtraction per edge, `n-1` edges, `O(n)` total after the down pass. Being able to derive that line on a whiteboard is the technical core of the topic. ## The condition that makes rerooting possible at all Rerooting is not a universal upgrade, and claiming it is is the fastest way to fail this question. The upward step needs to compute "the parent's aggregate **excluding** the contribution of this child". That requires the aggregate to be **invertible** — you must be able to remove one child's contribution from the combined value: - **Sums and counts** invert cleanly: subtract. - **Maximums do not invert.** You cannot recover "the best over the other children" by removing one value from a max. The standard workaround is exactly the two-branch trick used for path objectives — keep the top two child values, so excluding one child still leaves the correct best available in `O(1)`. - **Aggregates over a modular or saturating domain** may lose information when inverted; check before assuming. So the honest answer to "can we reroot this?" is: only if the per-node combine has an inverse, or a bounded-size summary that survives removing one child. ## The actual decision The interesting judgment is not whether `O(n)` beats `O(n^2)` — it does, eventually. It is whether *this* system is anywhere near eventually. Things to put on the table: | input to the decision | why it matters | | --- | --- | | measured `n`, and its growth curve | `n = 500` is 250k units of work; nobody notices. `n = 200,000` is 40 billion; everybody does. | | recompute frequency | Nightly batch tolerates quadratic far longer than a per-request path does. | | latency budget and its headroom | A job at 20% of budget with 3x annual growth has about two years. | | who maintains it | A two-pass inverted aggregate is materially harder to modify correctly than a loop that calls an obviously-correct function `n` times. | | how the objective is likely to change | If the aggregate might become a max or a constrained selection next quarter, the rerooted version may need rewriting anyway. | A defensible principal answer sounds like: *keep the naive loop, write down the `n` at which it breaches the budget, put a check in the job that warns when the input passes half of it, and take the rewrite when that alarm fires — not before.* The opposite call is equally defensible when the numbers say so; what is not defensible is rewriting on aesthetics, or refusing on habit, without either party knowing `n`. ## Landing the rewrite safely If you do take it, the naive version does not get deleted — it gets promoted to test oracle. Property-test the rerooted version against it on small random trees, including the shapes that break assumptions: a path, a star, a single node, two nodes. Assert the structural invariants you already have (subtree sizes sum correctly, the down pass agrees with a direct computation at the fixed root). Keep the two passes as separately named, separately testable steps rather than one clever recursive function, because the thing that goes wrong later is somebody adding a term to the aggregate and updating only one of the two passes. ## What a strong answer contains The derivation of the one-edge shift, the invertibility condition with the max case named as the exception, and a cost decision expressed in measured numbers rather than asymptotics. A candidate who gives only the third is hand-waving; one who gives only the first two has answered a senior question instead of this one.

  • What exactly changes when you move the root across a single edge in a total-distance DP?
    Everything inside the child's subtree gets one hop closer and everything outside gets one hop farther, so the new total is the old one plus n minus twice the child's subtree size. That is O(1) per edge, which is why a down pass for subtree sizes and sums plus an up pass gives every node's answer in O(n).
  • Which tree DP objectives can be rerooted, and which cannot?
    Rerooting needs the parent's aggregate minus one child's contribution. Sums and counts invert by subtraction, so they reroot directly. A maximum does not invert — you cannot un-max a value — so you keep the top two child values instead, which still answers 'best excluding this child' in O(1). Aggregates with no inverse and no bounded summary do not reroot.
  • How do you keep the rerooted version trustworthy after you have moved on?
    Keep the naive per-root loop in the test suite as the oracle and property-test the fast version against it on small random trees, including a path, a star and one- and two-node cases. Keep the down and up passes as separate named steps, since the usual regression is someone extending the aggregate in one pass only.

saying these in an interview costs you the question

  • Claims any tree DP can be rerooted
  • Says a maximum aggregate inverts like a sum
  • Rewrites to linear without measuring the actual n
  • Cannot state what changes when the root moves one edge
  • Deletes the naive version instead of keeping it as an oracle

context

resolving links…