finding two most distant elements in a binary tree

Question

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.

Answer 1

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));
 } 

copied code and images from here.

Answer 2

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.

Answer 3

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).