CODEWITHSUNDEEP
algorithmlanguage-agnosticbinary-tree
attwad
attwad

Reputation: 945

finding two most distant elements in a binary tree

I am looking for an algorithm that could find the two most distant elements in a binary tree, not looking for any special language, just for the algorithm.

Thanks.

Upvotes: 7

Views: 2343

Answers (3)

Pratik Deoghare
Pratik Deoghare

Reputation: 37172

Its called diameter of tree.

int diameter(Tree * t) // post: return diameter of t 
{ 
     if (t == 0) return 0; 
     int lheight = height(tree->left); 
     int rheight = height(tree->right);
     int ldiameter = diameter(tree->left); 
     int rdiameter = diameter(tree->right); 
     return max(lheight + rheight + 1, max(ldiameter,rdiameter));
 }

alt text

copied code and images from here.

Upvotes: 10

MAK
MAK

Reputation: 26586

Since this is a tree, there is only one path between any pair of vertices. This makes it easier for us to find the diameter of the graph.

The easiest way to do this is by doing two simple traversals of the tree. First, take any arbitrary node to be the root and compute the distances of each vertex from it using a simple DFS/BFS. Now, take the node that is the furthest from the root (this the first node of the most distant pair), and making it the new root, run another traversal of the tree computing distances from there. The most distant node from that is the other node of the pair.

The proof of why this works is left as an exercise.

There is also another way that computes the most distant pair by computing and comparing the most distant pairs for each subtree of the tree starting from an arbitrary node as the root (already mentioned in another answer).

Upvotes: 1

Li0liQ
Li0liQ

Reputation: 11264

What you are looking for can be named graph diameter. In order to get it you'll need to calculate the path from any vertex to any other and then go through all of them and find the largest one.
That can be achieved using Dijkstra's algorithm or by simply distance matrix (which can be achieved by powering the adjacency matrix) although it will take more time than Dijkstra's algorithm.

Upvotes: 4

Related Questions