Longest path in an undirected tree with only one traversal
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&gt;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 =&gt; helper(c) }
    heights = recursive.map { p =&gt; p[1] }
    paths = recursive.map { p =&gt; 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)
  }
}





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