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.