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 pseudocode 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.

October 13, 2011 at 10:38 pmFind the depth of a tree without using recursion « All About Algorithms