Question 3 [5] with sample solutions

For the bstree class specified in the attached definitions page (at the back of the exam), provide an implementation of the private insert method. (The implementation can be either recursive or not, your choice.)

Make sure that it maintains a valid binary search tree structure for the tree (i.e. smaller ids go in left subtrees) and correctly updates all node fields (including subtreeSize) as necessary. 
SAMPLE SOLUTION
bool bstree::insert(int idVal, float dataVal, node* &t)
{
   // if we found the insert point
   if (t == NULL) {
      t = new node;
      if (t == NULL) return false;
      t->id = idVal;
      t->data = dataVal;
      t->subtreeSize = 1;
      t->left = NULL;
      t->right = NULL;
      return true;
   } 

   // if they are trying to insert a duplicate
   if (t->id == idVal) 
      return false;

   // if the id belongs in the left subtree
   if (idVal < t->id) {
      if (insert(idVal, dataVal, t->left)) {
         t->subtreeSize++;
         return true;
      } else return false;
   } 

   // the value belongs in the right subtree
   if (insert(idVal, dataVal, t->right)) {
      t->subtreeSize++;
      return true;
   } else return false;
}