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

/*
   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
*/

#ifndef __MB_CX11_9__
#define __MB_CX11_9__

template < class btElementType >
class BST {
public:
   BST();
   int isEmpty();
                      // Precondition: None.
		      // Postcondition: None.
		      // Returns: true if and only if T is an empty tree
   btElementType& getData();
                      // Precondition: !this->isEmpty()
		      // Postcondition: None
		      // Returns: The data associated with the root of the tree
   void insert(const btElementType & d);
                      // Precondition: if d is a left child, then d must
                      //    be < parent->getData(); if d is a right child,
                      //    then d must be > parent->getData();
                      // Postconditions: T->retrieve(k)->getData() == d
   BST * retrieve(const btElementType & d);
                      // Precondition: none
		      // Postcondition: none
		      // Returns: if T contains a node matching d, then
                      //    T->retrieve(d)->getData() == d; otherwise,
                      //    T->isEmpty()
   BST * left();
                      // Precondition: !this->isEmpty()
		      // Postcondition: None
		      // Returns: (a pointer to) the left child of T
   BST * right();
                      // Precondition: !this->isEmpty()
		      // Postcondition: None
		      // Returns: (a pointer to) the right child of T
private:
   int           nullTree;
   btElementType treeData;
   BST *         leftTree;
   BST *         rightTree;
};

#endif