CODEWITHSUNDEEP
javarecursionbinary-tree
Eyjafjallajokull
Eyjafjallajokull

Reputation: 168

Find the longest path between any two nodes

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

Upvotes: 3

Views: 1708

Answers (4)

Alisa
Alisa

Reputation: 135

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.

Upvotes: 1

Mau
Mau

Reputation: 14468

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

Upvotes: 0

Rodrick Chapman
Rodrick Chapman

Reputation: 5543

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.

Upvotes: 0

James
James

Reputation: 5820

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

With a preference for depth-first

Upvotes: 1

Related Questions