Tree Diameter

The diameter is the maximum distance between any two vertices of a tree. This lesson measures distance in edges, so a single vertex has diameter 0. A tree may have several longest paths; a correct algorithm only needs to find one. Diameter endpoints are useful landmarks for distance problems, and the middle of a diameter identifies the tree center or centers.

Trying BFS from every vertex costs quadratic time. A special property of trees lets two traversals find a diameter in linear time. You will implement both endpoint searches and reconstruct an actual longest path, then justify why choosing a farthest vertex works.

Prerequisites: Tree Traversals (DFS and BFS); parent arrays and path reconstruction.

Build the idea

1. 1. Make the goal precise

   Take edges (1,2), (2,3), (3,4), (3,5), (5,6). Path 1 → 2 → 3 → 5 → 6 has four edges. No pair is farther apart, so the diameter length is 4. A diameter is not necessarily a root-to-leaf path for the root selected by the input or interface. Rooting at 3 gives maximum depth 2, while the diameter is 4.

2. 2. Make two endpoint searches

   Start from any vertex s and use BFS to find a vertex A of maximum distance from s. Then BFS from A and choose a vertex B of maximum distance from A. The distance from A to B is the diameter. Store parent pointers during the second BFS; follow them from B back to A and reverse the list to output the path.

   In the example, starting at 3 may choose A=1 or A=6, depending on ties. Either choice is valid. Starting the second search from 1 finds B=6 and distance 4. The implementation uses strict improvement when updating farthest, so tied farthest vertices are resolved by traversal order without affecting correctness.

3. 3. Why is a farthest vertex a diameter endpoint?

   Root the tree at the arbitrary start s, and let x–y be any diameter. Write t for the lowest common ancestor of x and y. A farthest vertex A has depth at least both depth[x] and depth[y]. If A lies below t, choose the endpoint lying in a different child branch of t from A, or t itself if t is an endpoint. The path from A to that endpoint goes through t. Replacing the other endpoint by A cannot shorten the path, because A is at least as deep.

   If A is not below t, its path to either endpoint goes through a common ancestor above t. Using depth[A] at least the depth of the opposite endpoint again gives a path at least as long as x–y. Since x–y was longest possible, the resulting path must also be a diameter. Thus A is an endpoint of some diameter, including when the first BFS has ties. The second BFS finds a farthest B from this endpoint and therefore reaches the diameter length.

4. 4. Why BFS works, and where the method applies

   BFS discovers vertices in increasing numbers of edges from its start. On a tree, DFS can also accumulate exact unweighted distances because each vertex has a unique path from the start; ordinary DFS distances are not shortest-path distances on general graphs. The two-search endpoint theorem relies on tree structure and must not be applied blindly to a cyclic graph.

   For a tree with nonnegative edge weights, accumulating unique-path weight sums also supports a two-search diameter method. The code here is strictly unweighted. Negative edge weights need a different treatment, particularly if endpoints must be distinct; do not silently reuse this implementation.

5. 5. Reconstruct and verify the answer

   The second parent array points toward A. Start at B and append vertices until reaching parent 0; the list ends at A. After reversing, consecutive labels must be actual edges, and path.size()−1 must equal distance[B]. N=1 naturally gives A=B=1, length 0, and path {1}. The longest path contains no repeated vertices because a tree has no cycles.

   Two traversals examine every vertex and edge only a constant number of times. The important optimization is not a faster queue: it is using the endpoint property to avoid N separate searches.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int bfs(int start,const vector<vector<int>>&graph,vector<int>&distance,vector<int>&parent){
    int n=(int)graph.size()-1;
    // Reset distances and parents for this search, including the new start vertex.
    distance.assign(n+1,-1);
    parent.assign(n+1,0);
    queue<int>q;
    q.push(start);
    distance[start]=0;
    int farthest=start;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        if(distance[v]>distance[farthest]){
            farthest=v;
        }
        for(int next:graph[v]){
            if(distance[next]!=-1){
                continue;
            }
            distance[next]=distance[v]+1;
            // This parent records the unique path back to this BFS start.
            parent[next]=v;
            q.push(next);
        }
    }
    return farthest;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int>distance,parent;
    // A farthest vertex from any start is an endpoint of some diameter.
    int a=bfs(1,graph,distance,parent);
    // Searching from that endpoint reaches the opposite diameter endpoint.
    int b=bfs(a,graph,distance,parent);
    // The second search parents reconstruct B-to-A; reverse for A-to-B output.
    vector<int>path;
    for(int v=b;v!=0;v=parent[v]){
        path.push_back(v);
    }
    reverse(path.begin(),path.end());
    cout<<distance[b]<<'\n';
    for(int i=0;i<(int)path.size();++i){
        cout<<path[i]<<(i+1==(int)path.size()?'\n':' ');
    }
}

Complexity analysis

O(N) time for two BFS runs and path reconstruction. O(N) space for adjacency lists, queue, distance/parent arrays, and the output path. The path has at most N vertices.

Example input and output

N, followed by N−1 edges of a valid unweighted tree. Print diameter length in edges, then one diameter path. Other longest paths are accepted.

Input

6
1 2
2 3
3 4
3 5
5 6

Output

4
6 5 3 2 1

The first BFS from 1 chooses 6; the second finds 1. The printed path crosses four edges. Reversing this path would also be correct.

Practical applications

Find worst-case travel distance, tree centers, and endpoints used in farthest-distance queries. In an unweighted tree with diameter endpoints A,B, the eccentricity of v is max(distance(v,A),distance(v,B)), a useful extension requiring its own justification.

Check your understanding

Why is maximum depth from an arbitrary root not necessarily the diameter?

Put it into practice

Print both middle vertex/vertices of your diameter path. Test paths with odd and even diameter lengths.