## Find the diameter of a tree.

First things first, what is the *diameter* of a tree? It is the maximum possible distance between *any two nodes* in a given tree. The nodes can or cannot be leaf nodes. Now that we know what the question means, let us start thinking about how we should approach this problem.

It should be inherently clear to you that recursion is the best way to go about this. So what kind of recursion-traversal should I adopt? A top-down one? Or a bottom-up one? You have previously seen examples of the bottom-up approach using recursion while finding depth of trees, etc. We can use the very same approach here as well.

Traverse down to the leaf nodes. Now move up one by one returning 1 from the leaf nodes. The value you should return from any node that is not a leaf node is the one that is greater (when comparing the one you get from the left and right branches) + 1. Also, at each node, compare the addition of the two values that you get from your left and right branches to a global variable that stores the maximum diameter of the tree that has been reached till now while going bottom->up. When you reach the root and then the first call of your function, the value returned is not important (and is not necessarily the diameter). The global variable has the diameter of the tree. 😉

An easy pseudo-code for this can be written as,

int tree_diameter=0;

int diameter ( node * curr ) //curr is ROOT for the first call

{

if ( curr->left NOT equal to NULL)

{

int l = diameter( curr->left );

}

if (curr->right NOT equal to NULL)

{

int r = diameter( curr->right );

}

if ( curr->left EQUAL to NULL and curr->right EQUAL to NULL)

{

return 2; //for leaf node

}

if ( l+r-1 > tree_diameter ) //checking if max length at this point is greater than currently stored diameter

{

tree_diameter=l+r-1;

}

if ( l>r )

return l+1;

else

return r+1;

}

You will finally get the diameter of your tree in the variable** tree_diameter** . Of course, it need not be a global variable and other ways can be used as an alternative to making the variable global. But that isn’t really what we are discussing in this post. You got the pseudo-code, right? Go to the bottom, start going up, at each point calculate current maximum length till you reach ROOT. Bomb! 🙂