Home > Applied Algorithms, Recursion, Tree > Find the diameter of a tree.

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! 🙂

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: