skip to content

In a tree DP for the longest path, why does each node combine two child branches but return only one?

level: seniorimportance: must knowfreq 50%

answer

  1. where does the longest run bend?
  2. a path enters and leaves one node
  3. the parent can extend only one branch
  4. two deepest branches versus one returned
  5. keep the finished answer in a separate global

basics

~20 s

A longest path bends at exactly one node, arriving up one branch and leaving down another, so every node tests its two deepest branches against a running global best. It returns only its single deepest branch, because a parent can extend just one.

solid answer

~50 s

Picture a patch-panel layout: switches joined by links with no loops, and you want the longest run of links between any two switches. Root the layout anywhere and do one post-order pass. Each node computes `depth = 1 + (deepest child depth)` and returns that single number upward, because a path passing *through* the parent can only continue down one of the parent's branches. Separately, at each node, the best path whose highest point is that node is `top1 + top2` — its two deepest child branches joined through it — and that value is compared against a global best. The two jobs need two different numbers, which is exactly why one return value cannot do both. The global answer can sit at any node, not the root; the whole pass is `O(n)` time and `O(height)` recursion space.

code

pseudocode · 14 lines
pseudocode
// switches joined by patch links; run length counted in links
best = 0
depth(v):                          // links below v on its deepest branch
    top1 = 0
    top2 = 0
    for c in children[v]:
        d = depth(c) + 1
        if d > top1:
            top2 = top1
            top1 = d
        else if d > top2:
            top2 = d
    best = max(best, top1 + top2)  // path bending at v, not extendable
    return top1                    // parent can extend only one branch

go deeper

for a junior

Know that the longest run in a tree need not touch the top node, and that each node looks at its two deepest downward branches rather than just one.

for a middle

Explain the split between the value returned upward — one branch — and the value folded into a global best — two branches — and why a single number cannot do both jobs.

for a senior

Demonstrate the single-pass discipline: one traversal, constant work per link, no repeated search from each node, plus how you would recover the two endpoints for an operator-facing report.

for a principal

Own the generalisation: which per-node aggregates compose upward at all, and what you standardise so every 'longest path' feature in the codebase is written the same way and tested against a brute-force oracle.

## The scenario A building's network closets are joined by patch links with no redundant loops, so the link graph is a tree. You want the longest run — the greatest number of links on the path between any two switches — because it bounds the worst hop count anything on the site can experience. The naive approach is to search outward from every switch and keep the largest distance found, which is one full traversal per switch: `O(n^2)`. The DP does it in one pass. ## The key structural fact Root the tree at any node you like. Now every path in the tree has a unique **highest** node — the one closest to the root among the path's nodes. Walking the path from one end, you go up to that node and then down the other side. This gives a partition of all paths by their topmost node, and it means: if, at every node, you compute the best path whose top is that node, then the maximum over all nodes is the global answer. Nothing is missed, and nothing is counted from two directions. A path topped at `v` uses at most two of `v`'s downward branches — one on the way in, one on the way out. So the best such path is `top1 + top2`, where `top1` and `top2` are the two greatest values of `1 + depth(child)` over `v`'s children (each treated as 0 when the child does not exist). A leaf gets `0 + 0 = 0`, correctly stating that a single switch has a zero-link run. ## Two numbers, two jobs Here is the distinction candidates most often collapse: - The value **returned to the parent** must be a *downward reach*: `top1`, the length of the deepest single branch hanging below `v`, plus the link to `v` itself when the parent adds it. The parent will attach this to its own path, and a path can only continue in one direction. - The value **compared to the global best** is a *finished path*: `top1 + top2`. It bends at `v` and is not extendable upward; handing it to the parent would let the parent add a link to something that is no longer an endpoint, producing a walk that is not a path at all. If you return the finished answer upward, you get numbers that are too large and paths that revisit `v`. If you only ever track `top1` and never combine two branches, you compute the tree's height, which is a different quantity — the height is the deepest single branch from the root, while the longest run may live entirely inside a subtree and never touch the root. ## Why the answer need not touch the root This is the anti-intuition to say out loud. Consider a root with one child; that child has two long branches of ten links each. The root's own two-branch combination is `11 + 0 = 11`, but the child's is `10 + 10 = 20`. The best path is topped at the child and never visits the root at all. Any implementation that reports the value computed at the root, rather than the running maximum over all nodes, gets this wrong — and it gets it wrong silently, since the two agree on symmetric test inputs. ## Cost and shape One post-order pass, constant work per link (a running top-one/top-two scan needs no sorting), so `O(n)` time and `O(height)` recursion space. Note that a running top-two scan is strictly better than sorting each node's children: sorting is `O(n log n)` overall for no benefit, and a candidate who sorts is signalling they have not thought about the per-node combine cost. The generalisation worth naming: any objective of the form "best thing that bends at a node" follows this same two-part shape — return an extendable partial upward, fold a completed candidate into a global best. It is a different shape from an objective like a constrained selection, where the root's own value already covers every case. Knowing which of the two shapes an objective has is the actual skill; the recurrence follows from it. ## What an interviewer probes next - Reporting the endpoints, not just the length: carry the endpoint reached by each node's deepest branch alongside the depth, and record the pair whenever the global best improves. - Weighted links: replace the `+1` with the link's length. With non-negative weights the argument is unchanged. - Very deep layouts: the recursion is `O(height)` frames, which on a daisy-chained run of closets is `O(n)` — the same explicit-stack conversation as any deep tree recursion.

  • Does the choice of which switch you root at change the answer?
    No. Under any rooting, every path still has a unique topmost node, and that node is where its two branches get combined. Rooting is only a device for ordering the computation, so any starting node gives the same global best. What does change is which node reports it.
  • How would you report which two switches the longest run connects, not just its length?
    Carry an endpoint alongside each node's deepest-branch value: the node returns both the depth and the switch that branch ends at. When a node's two-branch total beats the global best, record that pair of endpoints together with the node they bend at. Same single O(n) pass, one extra field per node.
  • What changes when patch links have different cable lengths instead of counting hops?
    Replace the +1 with the link's length; the recurrence is identical. With non-negative lengths the argument that a path bends at exactly one node still holds, so each node still combines its two longest branches and returns one. Time stays O(n).

Each node is a road junction. A through-route enters on one road and leaves on another, so a junction cares about its two longest roads — but it can only ever offer one of them to the junction above it.

saying these in an interview costs you the question

  • Assumes the longest path must pass through the root
  • Returns the best finished subtree answer up to the parent
  • Combines all child branches instead of the top two
  • Confuses the tree's height with the longest path
  • Runs a fresh search from every node, making it O(n^2)

context

resolving links…