A recursive method to find depth of a any(not necessarily complete) Binary tree

Question

I am trying to compute the depth of any(not necessarily complete) BST in O(log n) time recursively.

This is the algorithm I came up with:

//max() - returns the max of two numbers
int depth(root)
{
    if(root->left==NULL && root->right==NULL) //leaf
        return 0;
    else if(root->left!=NULL && root->right==NULL) //with right leaf
        return( max(depth(root->left),0)+1);
    else if(root->left==NULL && root->right!=NULL) //with left leaf
        return( max(0,depth(root->right)+1);
    else if(root->left->left==NULL && root->left->right==NULL && root->right->left==NULL&&root->right->right==NULL) // this a parent of two leaves
        return 1; 
    else// for the condition that this a parent of two sub roots
        return( max(depth(root->right),depth(root->left))+1);
}

Is this algorithm fine for calculating depth in O(log n) time?

Is there a better way?

Answer 1

That's O(n) time since you may traverse every node doing that. You can do a search on a binary search tree in O(log n) but you can't find the depth of a binary tree in anything less than O(n) unless you cache the depths as you build it or do something similar.

There are two special cases you may want to be aware of.

A perfect binary tree can have its depth determined in O(log n). This means every leaf is at the same level.

Complete and balanced binary tree can have its depth approximated in O(log n) or in O(1) if the number of nodes is known. This will be approximate however (+/-1 usually).

Answer 2

The only way you'll get O(log(n)) runtime is if you only examine one path, and the only way you will be able to get away with examining one path is if you know that the tree has uniform height, and this only is the case with full binary trees, which your question specifically stated is not the case.

Therefore, there is no O(log(n)) algorithm that will determine the depth of a given binary tree.

Answer 3

You can only find the deepest node of an unknown, unbalanced tree by looking at every leaf node, which requires traversing the lot as you are doing - O(n).

As for a "better" way, you can't make it a lesser Order, but you don't need quite such complex code to achieve your result. Here is marginally less efficient implementation (because it recurses one level deeper) which is much more readable and more robust (if you pass in a NULL root pointer it won't go pop) approach:

int depth(root)
{
    if (root == NULL)
        return(0);

    return(1 + max(depth(root->left), depth(root->right)));
}

Answer 4

A problem in C is that the function stack is not dynamicaly allocated on the heap, so at one point we will run out of space. Especially when each recursive call spawns two functions. In other words if your tree is somewhat balanced you will end up with log(N)^2 function calls. If you instead iterate over the left branches and recurse on the right ones, then the stack will not grow as fast.

int
depth(struct bt *root, int dl)
{
        int dr, dmr;

        for(dmr=dr=dl; root != NULL; dl++){
                if((dr = depth(root->right, dl+1)) > dmr) 
                        dmr = dr;
                root = root->left;
        }
        return(dl > dmr ? dl : dmr);
}

This is the way I.E. Quick Sort is implemented in many operating systems:

http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/qsort.c?rev=1.10;content-type=text%2Fx-cvsweb-markup