---
title: "Tree Diameter in Two Passes"
summary: "The double-BFS trick, the proof that it is correct, and the DP that beats it when you need more."
difficulty: core
tags: [trees, diameter, DP]
time: n
space: n
prereq: [trees/bfs]
see: [trees/distance, advanced-tree/centroid]
---

Pick any vertex $s$. Let $a$ be a farthest vertex from $s$. Let $b$ be a farthest vertex from $a$. Then $\operatorname{dist}(a,b)$ is the diameter.

```cpp diameter.cpp
pair<int,int> far(int s) {                       // -> {distance, vertex}
    vector<int> d(n, -1), par(n, -1);
    stack<int> st{{s}}; d[s] = 0;                 // DFS is enough on a tree!
    int best = s;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (d[u] > d[best]) best = u;
        for (int v : g[u]) if (d[v] == -1) { d[v] = d[u] + 1; par[v] = u; st.push(v); }
    }
    return { d[best], best };
}
auto [d1, a] = far(0);                            // pass 1: an endpoint of a diameter
auto [diam, b] = far(a);                          // pass 2: the diameter itself
```

:::note title="DFS is fine on a tree"
On a general graph you *must* use BFS (distances). On a tree there is exactly one path, so any traversal computes the true distance; DFS avoids the queue and, more importantly, also hands you the `par` array so you can reconstruct the diameter path itself.
:::

:::theorem title="Why it works"
$\operatorname{dist}(a,b)$ equals the diameter $D$.
:::

:::proof
$(\le)$ is trivial: $a,b$ are vertices, so their distance is at most the maximum over all pairs.
For $(\ge)$, let $P = x \leadsto y$ be a diameter path ($D = \operatorname{dist}(x,y)$).
Claim: $a$ is an endpoint of *some* diameter. Root the tree at $s$. Let $c$ be the highest (closest to $s$) vertex on the path from $s$ to $P$, splitting the tree at $c$ into the branch containing $x$ (length $p = \operatorname{dist}(c,x)$), the branch containing $y$ ($q = \operatorname{dist}(c,y)$), and the branch containing $s$ ($t = \operatorname{dist}(c,s)$).
Farthest from $s$ means $\operatorname{dist}(s,a) = \max(t+p, t+q) \ge t + D/2$, and $p+q = D$.
Now: $\operatorname{dist}(a,x) \ge \operatorname{dist}(s,x)$? Compare through $c$ — the standard exchange gives $\max(\operatorname{dist}(a,x), \operatorname{dist}(a,y)) \ge \max(t+p, t+q)$, because $a$ is at distance $\ge t$ from $c$ on the side opposite to whichever of $x,y$ is farther, so $a$'s eccentricity is at least $s$'s. Hence $b$, being farthest from $a$, satisfies $\operatorname{dist}(a,b) \ge \operatorname{ecc}(s) \ge \max(t+p, t+q)$ and choosing the worse of $x,y$ shows $\operatorname{dist}(a,b) \ge D$. ∎
:::

That proof is worth reading twice: the *only* thing used is "one branch at the split point", which is exactly the "path uniqueness" definition of a tree (@trees/properties (4)) — the argument collapses on a general graph, where double-BFS is only a 2-approximation, and that is a tight result, not laziness.

## When you need more than the number
:::example title="All pairs of vertices at distance exactly k"
Two options: (a) **edge contribution** — for each edge, count pairs whose path uses it; (b) **centroid decomposition** (@advanced-tree/centroid) in $O(n \log n)$ for "count pairs with distance ≤ K" including weights. Double-BFS cannot do either; the DP generalises.
:::

```cpp diameter-dp.cpp
// classic tree DP: longest downward chain + best path through u
int ans = 0;
function<int(int,int)> dfs = [&](int u, int p) {
    int best1 = 0, best2 = 0;                      // two deepest child chains
    for (int v : g[u]) if (v != p) {
        int c = dfs(v, u) + 1;
        if (c > best1) { best2 = best1; best1 = c; }
        else if (c > best2) best2 = c;
    }
    ans = max(ans, best1 + best2);                 // path passing through u
    return best1;
};
dfs(0, -1);
```

:::tip title="Pick the right one"
Two passes: 6 lines, no recursion, easy to write correctly — the diameter length.
DP: needed whenever the answer is per-vertex, per-edge, "through $u$", or when you must **avoid** the diameter's endpoints. If the problem only asks for the length, write the two passes under time pressure.
:::

:::demo id="traversal" caption="Start vertex choice changes the traversal order but never the second pass's answer — try `start = 0` and `start = 5`."
:::

:::problems
- [[CSES 1131]] Tree Diameter | https://cses.fi/problemset/task/1131 | easy | two BFS
- [[SPOJ PT07Z]] Longest path in a tree | https://www.spoj.com/problems/PT07Z/ | easy | two BFS
- [[CF 1000E]] We Need More Bosses | https://codeforces.com/problemset/problem/1000/E | hard | bridges + diameter
- [[CSES 2079]] Finding a Centroid | https://cses.fi/problemset/task/2079 | core | subtree sizes
:::