Tree Diameter, in depth: the double sweep, the top-two DP, centers and where the shortcut breaks

Definitions and the off-by-one to settle first

Fix the vocabulary before writing code, because half the bugs in contest and production code come from it. A tree has n vertices and n - 1 edges, connected and acyclic. The distance d(u, v) is the sum of edge weights on the unique u-v path; in an unweighted tree every weight is 1. The diameter D is the maximum of d(u, v) over all pairs, and a diameter path is any path that achieves it. There may be many: in a star with three leaves, every pair of leaves is one.

Decide early whether you count edges or vertices. Most graph texts count edges, so a single vertex has diameter 0 and a path on 5 vertices has diameter 4. Many interview problems, such as the diameter of a binary tree, also count edges, but some puzzles count vertices. Write the convention in the function's docstring and in the test names; an off-by-one here is silent.

The eccentricity ecc(v) is the distance from v to the vertex farthest from it. The diameter is the maximum eccentricity, the radius is the minimum, and the center is the set of vertices achieving the radius. In an unweighted tree the center is one vertex or two adjacent ones, and it sits at the middle of every diameter path. Placing a coordinator or root at the center minimises the worst-case distance to everything else.

The double sweep and why it works

The double sweep: pick any vertex s, find the vertex a farthest from s, then find the vertex b farthest from a. The distance d(a, b) is the diameter, and the a-b path is a diameter path. Each sweep is a single breadth-first or depth-first search, so the whole thing is O(n).

Why it works rests on one lemma: with nonnegative edge weights, for any start s, the vertex a farthest from s is an endpoint of some diameter. Sketch of the proof: let x-y be a diameter path and suppose a is not an endpoint of any diameter. Walk from s toward a. Either the s-a path touches the x-y path or it does not. If it touches at vertex m, then d(m, a) is at least the distance from m to the farther of x and y, otherwise one of them would be farther from s than a. Swap that end of the diameter for a and the path does not get shorter, so a is a diameter endpoint after all. If the paths do not touch, connect them through the unique tree path between them and the same exchange argument works with an extra connecting segment that only lengthens the new path. The comparisons need nonnegative weights at every step: adding a segment must never make a path shorter.

Once a is known to be a diameter endpoint, the second sweep is trivially right: the farthest vertex from a diameter endpoint is at distance D, by definition.

The one-pass dynamic program

The dynamic program roots the tree anywhere and, for each vertex u, computes down(u), the length of the longest downward path from u into its subtree. The longest path whose highest vertex is u joins the two deepest child branches: top1 + top2, where each branch value is down(child) + w(u, child). If u has fewer than two children, missing branches count as 0, which means the path stops at u. The diameter is the maximum of top1 + top2 over all u, because every path has exactly one highest vertex in a rooted tree.

Two things make the DP the better default. It needs one traversal instead of two. It is also not fooled by negative weights: it scores every highest vertex, so it never relies on the farthest-vertex lemma. When an edge is negative the 0 floor is still right, since stopping at u is always allowed. The double sweep's advantage is that it hands you the endpoints directly, which you need for centers and eccentricities, while the DP needs parent pointers and a second walk to recover the path.

Iterative implementation

The implementation below is iterative on purpose. A recursive DFS on a path-shaped tree of 100,000 vertices blows Python's default recursion limit and, in C++ or Java, can overflow the thread stack. Both functions accept the same adjacency list of (neighbour, weight) pairs; pass weight 1 for an unweighted tree to count edges.

def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    return adj

def far(adj, s):
    """Distances and parents from s, iteratively (no recursion limit)."""
    dist = [None] * len(adj)
    par = [-1] * len(adj)
    dist[s] = 0
    stack = [s]
    while stack:
        u = stack.pop()
        for v, w in adj[u]:
            if dist[v] is None:
                dist[v] = dist[u] + w
                par[v] = u
                stack.append(v)
    best = max(range(len(adj)), key=dist.__getitem__)
    return best, dist, par

def double_sweep(adj, s=0):
    """Diameter in edge-weight units; nonnegative weights only."""
    a, _, _ = far(adj, s)
    b, dist_a, par = far(adj, a)
    path = [b]
    while path[-1] != a:
        path.append(par[path[-1]])
    return dist_a[b], path[::-1]

def diameter_dp(adj, root=0):
    """Diameter by top-two branches; correct for any edge weights."""
    n = len(adj)
    order, par = [], [-1] * n
    seen = [False] * n
    seen[root] = True
    stack = [root]
    while stack:
        u = stack.pop()
        order.append(u)
        for v, _ in adj[u]:
            if not seen[v]:
                seen[v] = True
                par[v] = u
                stack.append(v)
    down = [0] * n
    best = 0
    for u in reversed(order):          # children before parents
        top1 = top2 = 0
        for v, w in adj[u]:
            if v == par[u]:
                continue
            branch = down[v] + w
            if branch > top1:
                top1, top2 = branch, top1
            elif branch > top2:
                top2 = branch
        down[u] = top1
        best = max(best, top1 + top2)
    return best

A plain stack gives DFS order, which is fine in a tree: each vertex is reached by exactly one path. The DP processes order in reverse, which guarantees every child is finished before its parent. The best = 0 start encodes the single-vertex path; if your definition says an empty tree has no diameter, guard n = 0 before calling.

Worked example: nine vertices, two sweeps, one DP

Take the tree in the figure: edges 0-1 (3), 1-2 (4), 1-3 (2), 3-4 (6), 3-5 (1), 0-6 (5), 6-7 (2), 6-8 (7). Start the first sweep at vertex 0. Distances from 0 are 0, 3, 7, 5, 11, 6, 5, 7, 12 for vertices 0 to 8, so a = 8 at distance 12.

Second sweep from 8: distances 12, 15, 19, 17, 23, 18, 7, 9, 0. The maximum is 23 at vertex 4, so D = 23 and following parents from 4 back to 8 gives the path 8-6-0-1-3-4, with weights 7 + 5 + 3 + 2 + 6 = 23.

Now the DP rooted at 0. Leaves 2, 4, 5, 7 and 8 have down = 0. Vertex 3 sees branches 6 (to 4) and 1 (to 5), so down(3) = 6 and its local best is 7. Vertex 1 sees branches 4 (to 2) and 6 + 2 = 8 (through 3), so down(1) = 8 and its local best is 12. Vertex 6 sees 2 and 7, so down(6) = 7 and local best 9. Vertex 0 sees 8 + 3 = 11 and 7 + 5 = 12, so its local best is 23, matching the sweep. The highest vertex of the diameter is 0, which is where the DP finds it.

Eccentricity, radius and center from the endpoints

With both endpoints a and b in hand, one more search gives every eccentricity: ecc(v) = max(d(v, a), d(v, b)). The proof uses the same lemma: the vertex farthest from v is always a diameter endpoint, and either a or b serves. So three linear passes (s, a, b) give the whole eccentricity table, the radius and the center.

In the example, d(v, 4) for vertices 0 to 8 is 11, 8, 12, 6, 0, 7, 16, 18, 23. Taking the larger of that and the distance from 8 gives eccentricities 12, 15, 19, 17, 23, 18, 16, 18, 23. The radius is 12 and the vertex center is vertex 0. In a weighted tree the true midpoint of the diameter may lie inside an edge: here it is 11.5 from vertex 8, half a unit along the edge from 0 toward 6. If you are placing something that must sit on a vertex, use the vertex with minimum eccentricity; if you are building a minimum-radius augmentation or splitting a tree in two, use the point on the edge.

The same endpoints answer dynamic questions. When a leaf v is attached to a tree whose diameter endpoints are a and b, the new diameter is max(D, d(v, a), d(v, b)), again with nonnegative weights. With an LCA structure for O(log n) distances, you can maintain the diameter of a growing tree with two distance queries per insertion. Joining two trees by an edge works the same way: the new diameter's endpoints are among the four old ones.

When the shortcut breaks

The double sweep is a theorem about nonnegative trees, and it fails quietly outside them.

• Negative edge weights. Take edges 0-1 (-5), 1-2 (4), 1-3 (3). From vertex 0 every other vertex is at negative distance, so the farthest vertex is 0 itself, the second sweep also returns 0, and the answer is 0. The true diameter is the path 2-1-3 with length 7. On 3,000 random trees with weights drawn from -10 to 10, the double sweep was wrong on 375 while the DP matched brute force every time. If any weight can be negative, use the DP.
• Forests. A sweep from s only sees s's component. Loop over unvisited vertices and take the maximum per component, and decide what the diameter of a disconnected input should mean.
• General graphs. On a graph with cycles the double sweep only gives a lower bound on the diameter; exact answers need all-pairs work in the worst case. Practical exact methods such as iFUB use repeated sweeps to prune, but they are not linear in the worst case. Do not ship a two-BFS graph diameter as exact.

Scale and data layout

Both methods are O(n) time and O(n) memory, so the engineering questions are about data layout. At tens of millions of vertices, Python tuple adjacency lists cost more than the algorithm; use flat parent and weight arrays or a compressed sparse row layout.

Weighted distances can overflow 32-bit integers on long paths with large weights; use 64-bit accumulators. With floating-point weights, ties between near-equal paths may flip between runs on different hardware, which matters if you hash or cache the chosen endpoints. Break ties by vertex id.

Testing against brute force

Test diameter code against brute force on many small random trees: compute the distance from every vertex and take the overall maximum, which is O(n squared) and obviously right. Random trees from "attach vertex i to a random earlier vertex" produce a good mix of paths, stars and bushy shapes. Also test the boundary cases by name: one vertex, two vertices, a path, a star, and all-zero weights. The harness below is the one used to check this article's claims.

import random

def brute(adj):
    return max(max(d for d in far(adj, s)[1]) for s in range(len(adj)))

def random_tree(n, lo, hi):
    return [(i, random.randrange(i), random.randint(lo, hi)) for i in range(1, n)]

for _ in range(3000):
    n = random.randint(1, 40)
    adj = build(n, random_tree(n, 0, 20))
    s = random.randrange(n)
    assert double_sweep(adj, s)[0] == diameter_dp(adj) == brute(adj)

Change the weight range to (-10, 10) and the assertion fails quickly, on the double sweep, while the DP still matches brute force. Keeping that variant as a test documents the precondition better than any comment.

What to do next

1. Pick the convention: edges or vertices, weighted or not. Write it into the function name or docstring.
2. Use the DP by default; use the double sweep when you also need the endpoints, after asserting all weights are nonnegative.
3. Make traversals iterative and store distances in 64-bit integers.
4. Derive eccentricities, the radius and the center from the two endpoints instead of running n searches.
5. Add a randomized brute-force test with nonnegative weights and a named negative-weight counterexample.
6. If the tree grows over time, keep the endpoint pair and update it with LCA distance queries rather than recomputing.
7. Continue with BFS and DFS foundations, iterative DFS with an explicit stack, the Euler tour technique for subtree queries, and Dijkstra's algorithm for weighted distances on general graphs.