Function that return average depth of a binary search tree

Question

I have the following binary tree structure, and I'd like to write a function that calculates and return the average depth of objects in a tree. Here is what I'm trying to do:

• calculate the total height of the tree
• divide total height/total nodes

However, I'm getting nowhere, and would love to have any helpful suggestions in terms of how can I go about implementing the algorithm.

typedef struct tree_s tree_t;
struct tree_s {
    int num;
    tree_t *left;
    tree_t *right;
}


int total_depth(tree_t *tree, int accum) {
    if (tree == NULL) {
        return accum; /* done */
    }
    accum = accum + total_depth(tree->left, accum+1);
    accum = accum + total_depth(tree->right, accum+1);
    return accum;
}

There seems to be something wrong with my recursive function total_depth, as i'm getting a ridiculously large number.

Answer 1

You should be doing something like:

int total_depth(tree_t *tree, int accum)
{
    if (tree == NULL) {
        return 0;
    }
    return accum +
        total_depth(tree->left, accum + 1) +
        total_depth(tree->right, accum + 1);
}

total_depth(root, 0);