//--------------------------------------------------------------------
//
//  Berman, Chapter 11                                           bst.C
//
//--------------------------------------------------------------------

/*
   Copyright (c) 1997 Oxford University Press. All Rights Reserved.
   This code is from "Data Structures via C++: Objects by Evolution", 
   published by Oxford University Press.  Permission is hearby granted 
   to use this code for any educational, non-commercial purpose, 
   provided this notice remains intact. 
   A. Michael Berman, Rowan University, berman@rowan.edu 
   http://www.rowan.edu/evolve
*/

#include "bst.h"

template < class btElementType >
BST < btElementType > :: BST()
{
   nullTree = 1;
   leftTree = 0;
   rightTree = 0;
}

template < class btElementType >
int BST < btElementType > :: isEmpty() const
{
   return nullTree;
}

template < class btElementType >
btElementType& BST < btElementType > :: getData()
{
   assert(!isEmpty());
   return treeData;
}

template < class btElementType >
void BST < btElementType >
:: insert(const btElementType & d)
{
  if (nullTree) {
      nullTree = false;
      leftTree = new BST;
      rightTree = new BST;
      treeData = d;
  }
   else if (d == treeData)
		  ; // do nothing -- it's already here!
   else if (d < treeData)
      leftTree->insert(d);
   else 
      rightTree->insert(d);
}

template < class btElementType >
BST < btElementType > *
BST < btElementType > :: retrieve(const btElementType & d)
{
   if (nullTree || d == treeData)
     // return a pointer to the tree for which retrieve was called
      return this; 
   else if (d < treeData)
      return leftTree->retrieve(d);
   else
      return rightTree->retrieve(d);
}

template < class btElementType >
BST < btElementType > *
BST < btElementType > :: left()
{
   assert(!isEmpty());
   return leftTree;
}

template < class btElementType >
BST < btElementType > *
BST < btElementType > :: right()
{
   assert(!isEmpty());
   return rightTree;
}