posted 7 years ago

Hi All,

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?

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

Campbell Ritchie

Marshal

Posts: 55761

163

posted 7 years ago

Please tell us the details of what they wanted. The first thing you ought to have done is ask what they meant by largest distance.

posted 7 years ago

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

SCJP - itspawan.com

William Brogden

Author and all-around good cowpoke

Rancher

Rancher

Posts: 13078

6

posted 7 years ago

I would use the flood fill algorithm being sure to complete all single steps first.

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

Bill

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

Bill

Embla Tingeling

Ranch Hand

Posts: 237

posted 7 years ago

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?

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

Posts: 3090

14

posted 7 years ago

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.

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

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

Posts: 237

posted 7 years ago

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.

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.

posted 7 years ago

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.

Pawan Chopra

SCJP - itspawan.com

Embla Tingeling

Ranch Hand

Posts: 237

posted 7 years ago

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.

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

Posts: 237

posted 7 years ago

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.

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.