Longest path in an undirected tree with only one traversal

Question Detail: 

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:

• Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$.
• Now start a DFS from $v'$ to find the vertex farthest from it. This path is the longest path in the graph.

The question is, can this be done more efficiently? Can we do it with a single DFS or BFS?

(This can be equivalently described as the problem of computing the diameter of an undirected tree.)

Asked By : emmy

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11263

Answered By : Raphael

We perform a depth-first search in post order and aggregate results on the way, that is we solve the problem recursively.

For every node $v$ with children $u_1,\dots,u_k$ (in the search tree) there are two cases:

• The longest path in $T_v$ lies in one of the subtrees $T_{u_1},\dots,T_{u_k}$.
• The longest path in $T_v$ contains $v$.

In the second case, we have to combine the one or two longest paths from $v$ into one of the subtrees; these are certainly those to the deepest leaves. The length of the path is then $H_{(k)} + H_{(k-1)} + 2$ if $k>1$, or $H_{(k)}+1$ if $k=1$, with $H = \{ h(T_{u_i}) \mid i=1,\dots,k\}$ the multi set of subtree heights¹.

In pseudo code, the algorithm looks like this:

procedure longestPathLength(T : Tree) = helper(T)[2]  /* Recursive helper function that returns (h,p)  * where h is the height of T and p the length  * of the longest path of T (its diameter) */ procedure helper(T : Tree) : (int, int) = {   if ( T.children.isEmpty ) {     return (0,0)   }   else {     // Calculate heights and longest path lengths of children     recursive = T.children.map { c => helper(c) }     heights = recursive.map { p => p[1] }     paths = recursive.map { p => p[2] }      // Find the two largest subtree heights     height1 = heights.max     if (heights.length == 1) {       height2 = -1     } else {       height2 = (heights.remove(height1)).max     }      // Determine length of longest path (see above)             longest = max(paths.max, height1 + height2 + 2)      return (height1 + 1, longest)   } } 

---

1. $A_{(k)}$ is the $k$-smallest value in $A$ (order statistic).