Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Jeanne Boyarsky
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Carey Brown
• Frits Walraven
Bartenders:
• Piet Souris
• Himai Minh

# Algorithm to find Nodes having largest distance in Binary tree.

Ranch Hand
Posts: 419
• Number of slices to send:
Optional 'thank-you' note:
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?

Marshal
Posts: 75648
354
• Number of slices to send:
Optional 'thank-you' note:
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.

pawan chopra
Ranch Hand
Posts: 419
• Number of slices to send:
Optional 'thank-you' note:
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.
300px-Binary_tree.svg.png

Author and all-around good cowpoke
Posts: 13078
6
• Number of slices to send:
Optional 'thank-you' note:
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

Master Rancher
Posts: 4188
57
• Number of slices to send:
Optional 'thank-you' note:
I suggest looking into Floyd-Warshall algorithm, Dijkstra's algorithm, and Johnson's algorithm.

Ranch Hand
Posts: 237
• Number of slices to send:
Optional 'thank-you' note:

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
Master Rancher
Posts: 4188
57
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 237
• Number of slices to send:
Optional 'thank-you' note:

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
Ranch Hand
Posts: 419
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 237
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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.

Ranch Hand
Posts: 40
• Number of slices to send:
Optional 'thank-you' note:
Thats very good. Cool!

pawan chopra
Ranch Hand
Posts: 419
• Number of slices to send:
Optional 'thank-you' note:
great work!

 We're being followed by intergalactic spies! Quick! Take this tiny ad! Free, earth friendly heat - from the CodeRanch trailboss https://www.kickstarter.com/projects/paulwheaton/free-heat