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.