Find the diameter of a tree

by manojgumber

Diameter of a tree is the maximum distance between two nodes in a tree. Hence we can see that maximum distance between two nodes will be always between leaf nodes. To find the distance between two leaf nodes, do the following–
Assuming that we are given pointer to any node of the tree.

  1. Do the BFS (breadth first Search) on the given node and find a node having maximum distance from the given node. The node having maximum distance from the given node will be a leaf node. Lets call it node1
  2. Now again apply the BFS on the node1 and find the maximum distance of any node from node1 . This distance is the diameter of the tree. Because node1 is a leaf of tree and BFS finds the shortest distance from node1 ( a leaf ) to all other nodes in tree. Clearly the node farthest from node1 will be a leaf and hence we will get the diameter of tree.
Advertisements