Question: 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
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. Navely, 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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
