// yasuhara, 15 Aug 2000


struct BinTreeNode {
  // item stored at this node
  int data;
  // ptrs. to children (left, right subtrees)
  BinTreeNode *left, *right;
};


// helper functions

int
max(int x, int y) 
{
  if (y > x) 
    return y;
  else 
    return x;
}


//////////////////////////////////////////////////////////////////////

// note: Some of these functions, as noted in the comments, only work
// on bin. search trees.  The rest will work on any bin. tree,
// regardless of item ordering.


// returns min. item in bin. search tree; fails on empty tree
int 
BSTFindMin(BinTreeNode *r) 
{
  assert(r != NULL);		
  if (r->left != NULL)
    return BSTFindMin(r->left);	// recursive case
  else				
    return r->item;		// base case
}


// returns max. item in bin. search tree; fails on empty tree
int 
BSTFindMax(BinTreeNode *r) 
{
  assert(r != NULL);
  if (r->right != NULL)
    return BSTFindMax(r->right); // recursive case
  else
    return r->item;		// base case
}


// returns min. item in general tree
int
treeMin(BinTreeNode *r)
{
  // if r == NULL, could return RAND_MAX instead (i.e. effectively infinity)
  assert(r != NULL);

  int minSoFar = r->data;

  // check right and left subtrees, if present
  if (r->left != NULL && minSoFar > treeMin(r->left)) 
    minSoFar = treeMin(r->left);
  if (r->right != NULL && minSoFar > treeMin(r->right)) 
    minSoFar = treeMin(r->right);

  return minSoFar;
}


// returns max. item in general tree
int
treeMax(BinTreeNode *r)
{
  // if r == NULL, could return -RAND_MAX instead (i.e. effectively -infinity)
  assert(r != NULL);

  int maxSoFar = r->data;

  // check right and left subtrees, if present
  if (r->left != NULL && maxSoFar < treeMax(r->left)) 
    maxSoFar = treeMax(r->left);
  if (r->right != NULL && maxSoFar < treeMax(r->right)) 
    maxSoFar = treeMax(r->right);

  return maxSoFar;
}


// returns number of items/nodes in tree
int 
treeSize(BinTreeNode *r)
{
  if (r == NULL)
    return 0;			// base case
  else
    // recursive case
    return 1 + treeSize(r->left) + treeSize(r->right);
}


// returns height of tree
int
treeHeight(BinTreeNode *r)
{
  if (r == NULL) 
    return 0;			// base case
  else
    // recursive case
    return 1 + max(treeHeight(r->left), treeHeight(r->right));
}


// returns number of leaves in tree
int
treeLeaves(BinTreeNode *r)
{
  if (r == NULL) {
    return 0;			// base case
  } else {
    if (r->left == NULL && r->right == NULL) {
      return 1;			// base case
    } else {
      // recursive case
      return treeLeaves(r->left) + treeLeaves(r->right);
    }
  }
}


// returns product of items in tree; returns 1 for empty tree
int 
treeProduct(BinTreeNode *r)
{
  if (r == NULL) 
    return 1;			// base case
  else
    // recursive case 
    return root->data * treeProduct(r->left) * treeProduct(r->right);
}


// returns sum of items in tree; returns 0 for empty tree
int 
treeSum(BinTreeNode *r)
{
  if (r == NULL) 
    return 0;			// base case
  else
    // recursive case
    return root->data + treeSum(r->left) + treeSum(r->right);
}


// returns average of items in tree
double
treeAverage(BinTreeNode *r)
{
  return (double)treeSum(r) / (double)treeSize();
}