Diameter of a tree

The Diameter of tree is the maximum length between two nodes. For example :
Consider the following tree of 7 nodes

Here, Diameter = 4 .

Algorithm

First, root the tree arbitarily.

For each node, we calculate toLeaf(node) which denotes maximum length of a path from the node to any leaf.

if node is leaf :
    toLeaf[node] = 0
else
    toLeaf[node] = 1 + max(toLeaf[child]) | for all child of node

We can use DFS to calculate toLeaf(node).

vector<int> toLeaf(n+1, 0); // n is no. of nodes
void dfs(int node){
    visited[node] = true;
    for(int child : tree[node]){
        if(visited[child])
            continue;
        dfs(child);
        toLeaf[node] = max(toLeaf[node], 1 + toLeaf[child]);
    }
}

Now calculate path_length(node) which denotes maximum length of a path whose highest point is node.

if node is leaf :
    path_length[node] = 0
else if node has only 1 child :
    path_length[node] = toLeaf[child] + 1
else
    Take two distinct child a,b such that (toLeaf[a] + toLeaf[b]) is maximum, then
    path_length[node] = (toLeaf[a] + 1) + (toLeaf[b] + 1)
    

Here is the implementation .

vector<int> toLeaf(n+1, 0), path_length(n+1, 0);
void dfs(int node){
    visited[node] = true;
    vector<int> length = {-1}; // allows us to handle the cases when node has less than 2 children
    for(int child : tree[node]){
        if(visited[child])
            continue;
        dfs(child);
        toLeaf[node] = max(toLeaf[node], 1 + toLeaf[child]); 
        length.push_back(toLeaf[child]);
    }
    int s = length.size(), m = min((int)length.size(),2);
    for(int i = 0; i < m; i++){
        for(int j = i+1; j < s; j++){
            if(length[i] < length[j])
                swap(length[i], length[j]);
        }
        path_length[node] += length[i] + 1;
    }   
}    

Finally, Diameter = maximum of all lengths in path_length. Therefore here, Diameter = 4.

Problems

• Tree Diameter

Reference

• Competitive Programmer's Handbook by Antii Laaksonen.