All longest paths

Our next problem is to calculate for every node in the tree the maximum length of a path that begins at the node. This can be seen as a generalization of the tree diameter problem, because the largest of those lengths equals the diameter of the tree. Also this problem can be solved in $O(n)$ time.

As an example, consider the following tree:

Let maxLength(x) denote the maximum length of a path that begins at node $x$. For example, in the above tree, maxLength(4)=3, because there is a path $4 \rightarrow 1 \rightarrow 2 \rightarrow 6$. Here is a complete table of the values:

Also in this problem, a good starting point for solving the problem is to root the tree arbitrarily:

The first part of the problem is to calculate for every node $x$ the maximum length of a path that goes through a child of $x$. For example, the longest path from node 1 goes through its child 2:

This part is easy to solve in $O(n)$ time, because we can use dynamic programming as we have done previously.

Then, the second part of the problem is to calculate for every node $x$ the maximum length of a path through its parent $p$. For example, the longest path from node 3 goes through its parent 1:

At first glance, it seems that we should choose the longest path from $p$. However, this does not always work, because the longest path from $p$ may go through $x$. Here is an example of this situation:

Still, we can solve the second part in $O(n)$ time by storing two maximum lengths for each node $x$:

• maxLength_1(x): the maximum length of a path from $x$
• maxLength_2(x): the maximum length of a path from $x$ in another direction than the first path

For example, in the above graph, maxLength_1(1)=2 using the path $1 \rightarrow 2 \rightarrow 5$, and maxLength_2(1)=1 using the path $1 \rightarrow 3$.

Finally, if the path that corresponds to maxLength_1(p) goes through $x$, we conclude that the maximum length is maxLength_2(p)+1, and otherwise the maximum length is maxLength_1(p)+1.