Diameter Of a Tree

Diameter of a tree is the longest path (Number of nodes) between two leaf nodes of the tree. It is also called width of the tree. For example, diameter of the below tree is 6 (red color nodes form part of the diameter)

           A
          / \
         B   C
        /   /  \
       D    E   F
             \
              G

Note that the diameter may not, necessarily include the root of the tree.

Solution:

At any given time the diameter of the tree (or sub-tree) is the largest of the following:

• Diameter of Left sub-tree (does not include current root in diameter)
• Diameter of Right sub-tree (does not include current root in diameter)
• The longest path that goes thru the root of tree = Height of LST + Height of Right Subtree + 1 (For the root)

The below code returns the diameter. It uses a helper function to compute the height of the subtree at any level. Code:

 /* Returns the diameter of a binary tree */
 int diameter(Node * root)
 {
    if (root == 0)
        return 0;
    // Get the height of left & right sub-trees
    int lh = height(root->lptr);
    int rh = height(root->rptr);
    // Diameter of left and right subtrees recursively
    int ld = diameter(root->lptr);
    int rd = diameter(root->rptr);
    return max( (lh+rh+1), ld , rd );
}
// Function to compute the height of a Binary tree
int height(Node* root)
{
    if(root == NULL)
        return 0;
    return ( 1 + max(height(root->lptr), height(root->rptr) ) ;
 }