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.
The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree.
Approach: First, we have to find two end vertices of the diameter and to find that, we will choose an arbitrary vertex and find the farthest node from this arbitrary vertex and this node will be one end of the diameter and then make it root to find farthest node from it, which will be the other end of diameter.
Calculate the height of each node of the tree (Assuming the leaf nodes are at height 1) using DFS. This gives the maximum distance from a Node to all Nodes present in its Subtree. Store these heights. Now, perform DFS to calculate the maximum distance of a Node from all its ancestors.
The respective farthest apart nodes from the middle are called nl and nr. Note that it is OK if there are multiple subtrees leading from the middle node which are considered part of the right part as long as one of the longest path (or the longest path if it is unique) is in the left part.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With