Tree Diameter

The diameter of a tree is the longest simple path between any two vertices — measured in edges, or in total weight for a weighted tree.

Method 1: two traversals — $O(n)$

1. BFS/DFS from any vertex; let $A$ be the farthest vertex found.
2. BFS/DFS from $A$; the farthest vertex $B$ and the distance to it give the diameter.

pair<int,long long> farthest(int src, int n) {
    vector<long long> dist(n, -1);
    queue<int> q; dist[src] = 0; q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : adj[u])
            if (dist[v] == -1) { dist[v] = dist[u] + w; q.push(v); }
    }
    int best = src;
    for (int i = 0; i < n; i++) if (dist[i] > dist[best]) best = i;
    return {best, dist[best]};
}
 
long long diameter(int n) {
    auto [a, _] = farthest(0, n);
    auto [b, d] = farthest(a, n);
    return d;
}

Why the first traversal lands on an endpoint

Let $P$ be a diameter path and $s$ any start vertex. Let $x$ be the vertex where the path from $s$ meets $P$. If the farthest vertex from $s$ were not an endpoint of $P$, you could replace one half of $P$ with the (strictly longer) path to that vertex, producing a path longer than the diameter — contradiction. ∎

Only for non-negative weights

The two-BFS argument fails with negative edge weights. Use the DP method below in that case.

Method 2: one DFS DP — $O(n)$

For each vertex, combine the two deepest downward paths through it.

long long best = 0;
 
long long dfs(int u, int p) {
    long long d1 = 0, d2 = 0;                 // two largest downward depths
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        long long d = dfs(v, u) + w;
        if (d > d1) { d2 = d1; d1 = d; }
        else if (d > d2) d2 = d;
    }
    best = max(best, d1 + d2);                // path bending at u
    return d1;
}

This version handles negative weights, generalises to “longest path with at most $k$ edges”, and is the natural starting point for any tree DP over paths.

Related quantities

Quantity	How
Center	the middle vertex (odd diameter) or two middle vertices (even) of the diameter path
Radius	$\lceil \text{diameter}/2\rceil$; the eccentricity of the center
Eccentricity of $v$	$\max (\mathrm{dist}(v,A),\mathrm{dist}(v,B))$ where $A,B$ are the diameter endpoints — an $O(n)$ answer for all vertices
Diameter of a forest	maximum over components
Diameter after adding an edge between two trees	connect their centers; new diameter is $\max (d_1,d_2,\lceil d_1/2\rceil +\lceil d_2/2\rceil +1)$

The eccentricity fact is a good one to remember: the farthest vertex from any $v$ is always one of the two diameter endpoints, so a single pair of BFS runs gives every vertex’s eccentricity.

Variants

• Diameter of a general graph — no shortcut; run all-pairs shortest paths.
• Weighted diameter with negative edges — the DFS DP works; two-BFS does not.
• Diameter under edge updates — link-cut trees or a segment tree over the Euler tour maintaining $\max (d_u+d_v-2d_{\mathrm{lca}})$.
• Longest path through a fixed vertex — the $d_1+d_2$ value at that vertex.
• Longest path in a tree of trees (virtual tree) — same DP over the virtual tree.
• Minimum height after rooting — root at a center; the height is the radius.

See also: Tree Center · Tree Fundamentals · Tree DP