Average depth of tree

[HG319]

I have project where I create a BST and now I have to compute the average depth of the tree, and then compute the ratio of the average depth to log2(n).
I am really unsure how to do this. I was hoping someone can help

[DyslexicChciken]

Provided that you have created the BST object and all its necessary functions, then this is one way to do this:

1. Have each node contain information about its height.

2. Have your BST class contain information about number of nodes(e.g., unsigned long long num_nodes). I will assume you have this already implemented.

3. Travel to each node recursively(pre-order, in-order, or post-order) and accumulate the height in a variable.

4. The accumulated sum of heights in step 3 is returned.

5. Use the returned value to calculate the average height(per node) in another function:

average height = total # of heights / total # of nodes

6. Calculate log_2(total # of nodes) and compute the ratio(in the same function as step 5 if you like):

average height / log_2(total # of nodes)

Alternatively, you can also create a variable in your BST class to store the height. But this is expensive to update if your tree is not balanced, just as counting the number of nodes is.

[HG319]

so just for average depth i wrote this but it is not giving me a proper answer
I have an object called int height in the my tree

int avgdepth(BST *node){
   int average=0, depth_sum=0;
   int LeftD, RightD;
        if ( t != NULL ){
            LeftD += avgdepth (node->left );
            RightD += avgdepth (node->right );
    }
        depth_sum=LeftD+RightD;
        average=depth_sum/Number_Of_Nodes();
        return average;
    }

[DyslexicChciken]

You want to initialize LeftD and RightD to 0, because otherwise they might get initialized with weird numbers.

I advise you to better modularize your code so it makes it easier to understand and debug.

1. Make a function to get height. If it returns height, then the bug isn't here.

2. Make a function to get number of nodes(should be similar). If it returns number of nodes correctly, then the bug isn't here.

3. Make a function that calculates average height and average height / log_2(total # of nodes). Test it using arbitrary numbers and if it returns correct values, then your bug isn't here.


Then afterwards all you really need is to take return value from (1) and divide by return value from (2) in function (3), as well as calculating the ratio. This you would only do once in function (3).