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.

__________________
If only life is as simple as C...

as you have said both have the complexity O(n)...
so any of these will do...
but it is better to write simple code.....
so that the next time you see it you know what it means....

and what does that Base Case 1 and Base Case 2 mean....
couldn't understand.....??
it would be nice if you could make it clear...

Actually, it would be nice if posters would read our rules and follow them. This thread is closed.