Definition: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

It can be shown that the diameter of a tree T is the largest of the following quantities:

  • the diameter of T's left subtree
  • the diameter of T's right subtree
  • the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
A pseudo program based on above algorithm is shown below:

  
int diameter(TreeNode t)
    {
    if (t == null) 
        return 0;
     
    int leftD  = diameter(t.left);
    int rightD = diameter(t.right);
    int rootD  = height(t.left) + height(t.right) + 1;

    return max(rootD, Math.max(leftD, rightD));
}

The problem with above algorithm is that this is not an O(n) algorithm but O(n^2). And the main culprit here is the height function. As height function is itself a linear function and is called for every node so this make the whole algorithm an O(n^2) affair.

This problem can be solved if we calculate the height with diameter itself and don't call height recursively for each node again and again. Pseudo code for the same is shown below:

  
int diameter2(TreeNode t, int* height)
{
    int lh = 0, rh = 0;
    int leftD = 0, rightD = 0;
 
    if(t == NULL)
    {
        *height = 0;
        return 0; /* diameter is also 0 */
    }
 
    leftD = diameter2(root->left, &lh);
    rightD = diameter2(root->right,&rh);
 
    /* Height of current node is max of heights of left and
    right subtrees plus 1*/
    *height = max(lh, rh) + 1;
 
    return max(lh + rh + 1, leftD, rightD);
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.