Helo guys, this is not specifically a C programming problem for the unix platform, but a problem i came across in class:

Find the average for a binary search tree:


typedef Struct SNode
{
double value;
SNode *leftChild;
SNode *rightChild;
} as SNode;


/*
* Solution 1
*/

double GetBSTSum (SNode *root)
{
// Base case 1
if( !root )
return 0;

// Base case 2
if( root->leftChild == NULL && root->rightChild == NULL )
{
return root->value;
}

// Recursive Case
else
{
return root->value + GetSum(root->leftChild) + GetSum(root->rightChild);
}

}

int GetNumNodes (SNode *root)
{
// Base case 1
if( !root )
return 0;

// Base case 2
if( root->LeftChild == NULL && root->rightChild == NULL )
return 1;

// Recursive case
else
return 1 + GetNumNodes(root->leftChild) + GetNumNodes(root->rightChild);


}

double GetAvg (SNode *root)
{
double dTotal = GetBSTSum( root );
int iNumNodes = GetNumNodes( root );

return dTotal/iNumNOdes;
}



/*
* Solution 2
*/
void GetTotalAndCount (SNode *root, double & dSum, int & dCount)
{
if (!root)
return;
else
{
GetTotalAndCount (root->leftChild, dSum, dCount);
GetTotalAndCount (root->rightChild, dSum, dCount);

dSum += root->value;
dCount++;
}
}

double GetAvg (SNode *root)
{
double dTotal = 0;
int iNumNodes = 0;

GetTotalAndCount (root, dTotal, iNumNodes);

return dTotal/iNumNOdes;
}




Questions:

For solution 1, would it be better to use base case 1 or base case 2? (assuming of course that a leaf node will have null pointers for its children)

Is there any reason to choose solution 2 over solution 1 besides the fact that we only need to iterate through the tree once? Both solutions are O(n).

Any comments appreciated.