Paths on the tree You are given T a undirected tree ie conne

Paths on the tree

You are given T, a undirected tree (i.e. connected and acyclic graph). The objective is finding two nodes u, v of T s.t. the distance (i.e. the number of edges along the unique path between u and v) is the maximum. Naïvely, you can try all possible pairs of nodes but this is very slow. Here is a very simple algorithm for this problem that runs in linear time. You start from any node s as the source and perform BFS. Let u be the node with the largest distance from s (i.e. at the largest level). Then you perform a second BFS: this time you use u as the source. Let v be the node with the largest distance from u. Now, prove this claim: the distance between u and v is the largest possible distance between any two nodes on the tree.

Solution

For the node s, u is the farthest node and there is no other node n in T whose distance from s is greater than u.

Hence, u represents 1 corner of the tree.

Using u as source, we find the node v which has the maximum distance. Arguing as before, v also represents another corner of the tree.

Hence, the distance between 2 corners(u and v) is the maximum possible distance between any 2 nodes of the tree.