Find the longest path between any two nodes

3
votes

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) )

4
javarecursionbinary-tree
Please post whatever code you have written so far and we will help. However, I (for one) am not going to give you a solution. It would defeat the purpose of your homework ... which is to get you to learn to write programs for yourself. – Stephen C
You could find some help more here: stackoverflow.com/questions/1664390/… – letsc

4 Answers

1
votes

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

With a preference for depth-first

1
votes

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.

0
votes

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.

0
votes

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