Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 779
attwad Avatar asked Mar 15 '10 10:03

attwad


People also ask

How do you find the distance between two points in a binary tree?

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.

How do you find the farthest node in a 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.

How do you find the maximum distance of a tree?

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.

What nodes are farthest apart?

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.


2 Answers

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.

like image 150
Pratik Deoghare Avatar answered Sep 21 '22 21:09

Pratik Deoghare


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.

like image 24
Li0liQ Avatar answered Sep 18 '22 21:09

Li0liQ