Finding the 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 without looking for any special language, only for the algorithm.

Thanks.

Answer 1

It is called the diameter of the 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)); } 

The copied code and images from here .

Answer 2

What you are looking for can be called the diameter of the graph . To get it, you will need to calculate the path from any vertex to any other, and then go through all of them and find the largest one. This can be achieved using the Dijkstra algorithm or simply a distance matrix (which can be achieved by including an adjacency matrix ), although it will take longer than the Dijkstra algorithm.

Answer 3

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

The easiest way to do this is to do two simple tree walks. First, take any arbitrary node as the root and calculate the distance from each vertex from it using simple DFS / BFS. Now take the node that is farthest from the root (this is the first node of the most remote pair), and making it the new root, start another traversal of the trees calculating the distances from there. The farthest node from this is another node of the pair.

The proof of why this works remains as an exercise.

There is also another way to calculate the most remote pair by calculating and comparing the most remote pairs for each subtree of the tree, starting with an arbitrary node as the root (already mentioned in another answer).