Home > Applied Algorithms, Recursion, Tree > Find the depth of a tree using recursion

Find the depth of a tree using recursion

Recursion questions on trees tend to follow the same pattern. Recursion can always be the most helpful tool when dealing with trees unless the size of the tree is very large. (Since it would render your program out of memory)

Let us start with the algorithm. The way to go about such questions is to start at the root and recurse down to the leaf nodes. Once you are there, go back, increasing the count by 1 every time as you move back up. Now at every node, compare the values you receive from the left and right (assuming binary) and pass up the value that is greater (+1). At the root, you would end up getting the depth of the tree. 🙂

Hope you got the concept because I’ll go on to write the pseudo-code now,

int depth ( node * current)

{

if (current->left NOT equal to NULL)

{

int l = depth ( current->left);

}

if (current->right NOT equal to NULL)

{

int r = depth (current->right);

}

if (current->right equal to NULL and current->left equal to NULL)

{

return 1; //for leaf nodes

}

if(l>r)

return l+1;

else

return r+1;

}

So if you understood the concept I explained, you’ll understand the code too. If you have any problems, feel free to post a comment. 🙂

Coming out soon with how to find the depth of a tree without using recursion. Stay tuned.

Advertisements
  1. No comments yet.
  1. October 13, 2011 at 10:38 pm

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: