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?

Pawan Chopra

SCJP - itspawan.com

Pawan Chopra

SCJP - itspawan.com

The last pixel to be "colored" will be furthest away.

Bill

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?

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.

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.

Pawan Chopra

SCJP - itspawan.com

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.

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.

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |