Chapter 2 · Trees
Distance, Radius, Eccentricity
dist on trees and graphs, the centre-of-a-tree theorem, and why two BFS passes are enough.
For a connected (unweighted) graph:
- dist(u,v) = number of edges on a shortest path,
- ecc(v) = maxu dist(v,u) — how far v is from the worst vertex,
- radius r = minv ecc(v), attained at a centre,
- diameter d = maxu,v dist(u,v), attained at a peripheral pair.
Always r ≤ d ≤ 2r.
Pick a peripheral pair a,b with dist(a,b) = d and a centre c. By the triangle inequality d = dist(a,b) ≤ dist(a,c) + dist(c,b) ≤ 2 ecc(c) = 2r, and r ≤ d because min ≤ max. ∎
On trees the picture is rigid:
The centre of a tree is a single vertex or a single edge (two adjacent vertices). Equivalently: repeatedly delete all leaves; what remains — one vertex or one edge — is the centre, the diameter path passes through it, and ecc is the same for both centre vertices in the edge case.
Every longest path (diameter) in a tree is unique up to reversal between its endpoints… more precisely: all diameters share the centre. Leaf-stripping decreases the eccentricity of every surviving vertex by exactly 1 and cannot create a new longest path, so the process ends on the set of vertices of minimum eccentricity. Since the tree has no cycle, the survivor set is connected: one vertex or one edge. ∎
Algorithmically, leaf-stripping is a multi-source BFS from all leaves with a queue — O(n), and it also solves "minimum height rooted tree" (LeetCode-style find root of minimum height tree), and the tree centre used as the root of a centroid-like decomposition heuristic.
#Distances between many pairs at once
Two questions that look like "run BFS n times" but are not:
The naive O(n2) becomes two DFS passes: for each vertex the farthest vertex is an endpoint of some diameter — this is false in general, but for a tree the following DP is exact: keep down[u] (best distance into the subtree) and up[u] (best distance via the parent), then ecc(u) = max(down, up). Combining children needs the two largest down values, hence O(n). The rerooting code is below.
// down1[u], down2[u]: the two deepest downward paths through u
void dfs1(int u, int p) {
for (int v : g[u]) if (v != p) {
dfs1(v, u);
int cand = down1[v] + 1;
if (cand >= down1[u]) { down2[u] = down1[u]; down1[u] = cand; }
else if (cand > down2[u]) down2[u] = cand;
}
}
// up[u]: best path going through the parent of u
void dfs2(int u, int p) {
for (int v : g[u]) if (v != p) {
int via_parent = 1 + max(up[u], (down1[v] + 1 == down1[u] ? down2[u] : down1[u]));
up[v] = max(up[v], via_parent);
dfs2(v, u);
}
}
// ecc[u] = max(down1[u], up[u]); radius = min ecc; diameter = max eccdown1[v] + 1 == down1[u]When the best path through u is the one coming from v, you must not reuse it — take the second best instead. Every rerooting DP has this "exclude the child you came from" step; getting it wrong is the most common silent bug in tree DPs, and it is exactly why keeping the two best values (not just the best) is worth the extra array.
#General graphs
- All-pairs BFS: O(nm) — fine for n ≤ 2000, better than Floyd's O(n3) when the graph is sparse.
- Unweighted with small integer weights: 0-1 BFS / Dial, 0-1 BFS, Dial, Potentials, Johnson.
- Weighted: run Dijkstra per source (O(nm + n2 log n)) or Floyd–Warshall (Floyd–Warshall).
- Approximating diameter in huge graphs: two BFS passes give a 2-approximation in any graph, and O(√(log n))-approximation needs more machinery; the exact value needs tildeΘ(nm) under SETH, which is the standard "you cannot do better" citation.
Same graph: the BFS layer numbers are exactly dist(root, ·); DFS's are not. That is the whole difference between the two traversals.