This is a question asked in interview. I have searched allot but could not get the answer for this. I want to write an algorithm to find nodes having largest distance in a binary tree. Can any one help on this?

I have a binary tree. Now what I want is I want to write an algorithm which will give longest path between two nodes. As shown below we can say 5/11 and 4 has longest path between each other. I hope these details will help you to understand the problem.

pawan chopra wrote:I have a binary tree. Now what I want is I want to write an algorithm which will give longest path between two nodes.

In a binary tree you cannot speak about the longest path between two nodes really because there's just one path between two nodes. So maybe it's a trick question. Or maybe you want to identify the longest path between ANY two nodes in the tree?

Also in your example tree, what are the numbers? There are doubles so they cannot be node identifiers. Do they represent something else like length for example?

Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007

9

posted

0

Silly me, I overlooked the "binary tree" part of the problem. That makes this considerably simpler than the algorithms I suggested. Ignore my last post.

uj nossnahoj wrote:In a binary tree you cannot speak about the longest path between two nodes really because there's just one path between two nodes. So maybe it's a trick question. Or maybe you want to identify the longest path between ANY two nodes in the tree?

The latter is certainly how I would interpret the original question at this point.

Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237

posted

0

Mike Simmons wrote:The latter is certainly how I would interpret the original question at this point.

Me too: Find the longest distance between any two nodes in a binary tree (and the numbers in the nodes are node identifiers).

In that case I have a suggestion.

First consider a "complete" binary tree. It's a tree where all nodes are present down to a certain depth. Say we have a complete tree of depth 3 and the nodes are numbered from left to right,

1
2 3
4 5 6 7

Here 2 and 3 are children of 1, and 4 and 5 are children of 2, etcetera. Now if we instead write the numbers in binary representation we get,

1
10 11
100 101 110 111

Note how the number of digits in the binary number corresponds to the node's depth in the tree.

Most binary trees won't be complete like this. Some nodes will be missing. Still the nodes in any binary tree can be given the numbers they would have in a complete tree. This enumeration can be done in one recursive traversal.

Now to calculate the distance between two nodes we strip off all equal binary digits from the left. The number of bits in each number now corresponds to the depth from the closest common parent node. These depths uniquely determines the distance between the nodes!

An example. Determine the distance between 100 and 101,

10|0
10|1

Both numbers have depth 1 from the closest parent (meaning they're direct children). The distance is 1+1 = 2.

Next example,

1|00
1|11

Both numbers have depth 2 from the closest parent (meaning they're grandchildren). The distance is 2+2=4

Next example,

10|
10|0

Here one number actually is the parent so its depth is 0. The other one has depth 1 (a child). The distance is 0+1=1.

Thanks to all of you....I am happy to see algorithms for solving this and also I am sad that I will have to study all of them . One thing I would like to ask I have done my engineering in Electronics but now I have been working with Java from last 3 years. Can any one suggest me how can I start and from where I should start learning all these basic things. Algorithms and datastructures . My friends suggested me to learn C language and datastructures and algorithms and all.

Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237

posted

0

pawan chopra wrote:Thanks to all of you....I am happy to see algorithms for solving this and also I am sad that I will have to study all of them . One thing I would like to ask I have done my engineering in Electronics but now I have been working with Java from last 3 years. Can any one suggest me how can I start and from where I should start learning all these basic things. Algorithms and datastructures . My friends suggested me to learn C language and datastructures and algorithms and all.

Well, I've presented a specific algorithm for the problem at hand. The other algorithms are more general in nature and requires that you reformulate the problem. Still you need to be able to traverse a binary tree recursively and you need to find a way to represent and manipulate the "binary numbers" used in the solution.

And you don't have to learn C to learn about algorithms & data structures. Java is just fine.

Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237

posted

0

Here's a solution based on my suggestion. The "binary numbers" I introduced really are just an encoded form of paths from the root node down to any specific node. So instead I've used a node list to represent those numbers.

The principle is that to calculate the length between two nodes you first find the closest common ancestor to the nodes. The distance between the nodes then is the sum of the distances from each node to the common ancestor.

The algorithm first collects the node lists of all nodes in one recursive traversal of the tree. Then the distance between all node pairs are calculated and stored in a list. This list is then sorted on distance. Finally the list is printed.