Find the longest path between any two nodes.

Question

I have a binary tree. I need to write Java recursive method that will give longest path between two nodes.

For example longest path if following tree is 7 (7-8-5-13-15-18-16-17).

http://img294.imageshack.us/img294/130/treeb.jpg

What's the way to resolve this problem?

(The method: public static int longestPath(Node n) )

Answer 1

Considering this is homework I'd look at Depth-First search and Breadth-First search.

With a preference for depth-first

Answer 2

Here is a clue:

First, can you solve this simpler problem?

Find the max from a list of integers.

Second, a new path occurs whenever a node has children.

Answer 3

Also note that the problem is NP-complete, so you probably won't be able to find a polynomial algorithm.

Answer 4

To start with, you can write a function that returns the height of the tree, which is equal to the length of the longest path.