recursive findaverage function for Binary search tree

[Asif_NSU]

I need to add a recursive function, called findaverage() into BST class that takes as input the root of the BST and returns the average of the entire integer items stored in that BST of integers.

Plz help me with this function especially without using any static variables.

[Chainsaw]

How about something along these lines, assuming every node has a value 'myValue' and a left and right child pointer:

int BST::findTotal( int &nodesFound )
{
    nodesFound++;
    int total = myValue;
    if (left != NULL) total += left->findTotal( nodesFound );
    if (right != NULL) total += right->findTotal( nodesFound );
    return total;
}
. . . 
    // Find average:
    int nodesFound = 0;
    int total = root.FindTotal( nodesFound );
    printf( "average is %d in %d nodes\n", (nodesFound == 0) ? 0 : total/nodesFound, nodesFound );

[Asif_NSU]

i wanted to see the findaverage function independent. Most of my friends solved the problem using a global variable total and some did using static variables(none of which i liked). There are two things involved into finding the average recursively. First i need to find the total which i can do using a separate recursive function. Then i can also write a recursive function to count the number of nodes. The last thing is to divide the total with the number of treenodes. But the problem was set to test if we could incorporate the functionality of these two recursive functions into one recursive function in order to find the average. I think i once read something called running sum and running average. I think that might help me do this the way i want. But the problem is i dont quite remember it clearly. Can anyone help?

[Chainsaw]

I suppose with floating point numbers you could keep a running average as you go, but why do this extra weirdness when you can get the total and total count recursively? Is it just because that's the assignment?

[Chainsaw]

And, using statics and globals really undermines the meaning of a recursive function, in my humble opinion. It also makes the function non-thread-safe, which may be ok in this instance but isn't a good general-purpose solution.

At the very least, you could have a class that contains member variables so you don't need globals and statics; something like:

class ABSTAverage
{
public:
    ABSTAverage()
    {
        m_total = 0;
        m_count = 0; // replacement for globals
    }
    int findAverage( BST* node )
    {
        if (node == NULL) return 0;
        m_count++;
        m_total += node->myValue; 
        findAverage( node->left );
        findAverage( node->right );
        return m_total / m_count;   // return the average
    }
protected:
    int m_total, m_count;
};

And that would be better, but it still seems sorta inelegant.

[Asif_NSU]

I suppose with floating point numbers you could keep a running average as you go, but why do this extra weirdness when you can get the total and total count recursively? Is it just because that's the assignment?

>>I know it's weird, and yes thats just bcos it was the assignment. You said i could do this with running average, could u plz show me how?That's what i have been trying to do. Unfortunately, i dont remember that running avg thing very well.

using statics and globals really undermines the meaning of a recursive function, in my humble opinion.

>>I do agree with u, and that's why i have been looking for something different.

you could have a class that contains member variables so you don't need globals and statics

>>But this findaverage() was supposed to be a member function of my BST(binary search tree) class. Making another class would somehow complicate things(right?), and the assignment asked us to write only a recursive function to do the job. I had to do it something like this:

int main()
{
     BST mytree;
    //insert nodes  into the tree
    cout<<"\nAVERAGE = "<<mytree.FindAverage(mytree.getRoot());//passed the root of tree to the findaverage function
    return 0;
}

[Chainsaw]

I'm no math major, but the running average idea is something like this:

can you add these as static members to BST? Static because you need this for the whole tree, not just for a single node:

...
static double m_averageSoFar; // used only in findAverage()
static double m_averageCount; // ditto
...

and those get initialized to zero SOMEHOW when you call findAverage for the very first time. Ick ick ick. Like "if (node == &root) <set statics to zero>" I hate that!

for each node, you would say something like:

// reconstitute the total and add this node's value
double totalSoFar = (m_averageSoFar * m_averageCount) + (double)myValue;
m_averageCount += 1.0; // account for this new node
m_averageSoFar = (totalSoFar / m_averageCount); // running average

Have you considered the possability that the lesson here is that some things don't directly lend themselves to a recursive algorithm? That maybe something like computing the total value and count might be well suited to recursion, but average needs:
<setup>
call a different recursive function (like getting total value/count)
<finish>

?
Maybe its a trick question! :-)

[Asif_NSU]

thanx for all that. I will be working on it and will let u know if i can pull it through.