Algorithm is as follows:

1.pick any leaf in the tree, and name it as L1

2.find the longest path from L1 in the tree. We name the leaf at the other end of the path as L2. The complexity of this step is θ(m), where m = c*n(0.5≤c≤1).

3.find the longest path from L2 in the tree. We name the leaf at the other end of the path as L3. This path(from L2 to L3) is the longest path in the whole tree. The complexity of this step is θ(n).

Therefore, the complexity of the whole algorithm is θ(m+n).

In the best case scenario, m=0.5*n, thus the total complexity is θ(1.5*n)= θ(n).

In the worst case scenario, m=n, thus the total complexity is θ(2*n) = θ(n).

So the complexity of the whole algorithm is θ(n).

 

Prove: the key of the prove is to demonstrate that L2 must be one of the leaves on the longest path.

Assuming there is a path(P’) which is longer than the path(P) we get from the algorithm, and L2 is not one of the leaves on this path. We name the 2 leaves on the longest path as x and y.

Condition1: P and P’ have a common node like figure as follows:

*We ignore the other nodes, edges, and leaves in the tree.

Py

 

P1

 

P2

 

Px

 

y

 

x                       

 

 

           

 

L2

 

L1

 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               

P=P1+P2, P’=Px+Py,

Based on assumption, Px+Py>P2+P1, and Px+Py>Px+P2àPy>P2à P1+Py>P1+P2, this is a contradiction to the condition that P(P1+P2) is the longest path from L1.

 

P0

 

Px

 

Py

 

P2

 

P1

 

x

 

y

 

L1

 

L2

 
Condition1: P and P’ have no common node but are connected through path P0(P0>0):                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           

Based on assumption, Py+Px>Py+P0+P2.

Since P2+P1 is the longest path from L1, P1+P2>P1+P0+Px.

So Py+Px+ P1+P2> Py+P0+P2+ P1+P0+PxàP0<0, this is a contradiction.

Conclusion: L2 must be one of the leaves on the longest path.