Longest path in a binary tree

The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7. In this example the longest path passes through the root node. Sometimes it may not pass through the root. Checkout the next example.

The longest path 27-28-24-36-42-59-55 does not include the root node.

Here is how we can find the longest path recursively. We know that the height of the binary tree is the longest path from the root node to any leaf node.(Read this post to know more). Diameter is the maximum of the following.

Height(left subtree) + Height(right subtree) + 1
Diameter(left subtree)
Diameter(right subtree)

Here is the C++ implementation of the above. This program calculates the number of nodes on the longest path. The time complexity for this solution is O(n²). For optimal implementation, you can checkout this post.