/************************************
 In this file you will see how to design Binary Search Tree (BST) in
 a class. To keep the philosophy of OOP straight, the designer of the 
 BST should not assume any knowledge of the data (e.g. struct, class, 
 array) stored in the tree node. The users of the BST class should 
 decide how to order their records.  Unless the user declare the BST 
 in simple data type, he/she needs overload the comparison operators 
 in accordance with his/her data (e.g. struct, class, array)
 
 Unlike the old-fashion design (as the one in oldy-bstree.cpp), this 
 requires a very careful implementation, and sometimes it is a big 
 pain on the neck. But in the long term it is worthwhile, since you 
 don't have to redesign the tree if you want a BST of different data
 type. 
 
 -- Chung-Chih Li, 5-1-2003
*************************************/

////  Header file for Tree
////

#include <iostream>
using namespace std;


///////////////////////////////////////////////////////////////////
/////////////////// Binary Search Tree  Template  /////////////////
///////////////////////////////////////////////////////////////////
template<typename T>
class BST
{
public:
    BST();
    BST(BST<T> & bst);
    T max();
    T min();
	T searchdata(T rec);
    void print();
	void insert(T rec); 
    void remove(T rec);  
    bool isempty();
    ~BST();  // Delete every node in the list.
private:
    bool empty;
    T *data;
    BST *left;
    BST *right;
};


template<typename T>
BST<T>::BST()
:data(NULL), left(NULL), right(NULL) {}


template<typename T>               // Copy constructor
BST<T>::BST(BST<T> & bst)    
{
    if (bst.data==NULL)
    {
        data = NULL;
        left = right = NULL;
        return;
    }
    data = new T;
    *data = *bst.data;           // make sure this is ok. 
    if (bst.left != NULL)
        left = new BST<T>(*(bst.left));
    else
        left = NULL;
    if (bst.right != NULL)
        right = new BST<T>(*(bst.right));
    else
        right = NULL;
}



template<typename T>   
bool BST<T>::isempty()
{
	if (data == NULL) return true;
	return false;
}

template<typename T>   
void BST<T>::insert(T rec)
{
    if (data == NULL)
    {
        data = new T;
        *data = rec;
        return;
    }
    if (*data > rec) // go to the left;
    {
        if (left == NULL) left= new BST<T>;
        left->insert(rec);
    }
    else 
    {
        if (right == NULL) right= new BST<T>;
        right->insert(rec);
    }
} 


template<typename T>   
void BST<T>::remove(T rec)
{
    if (data == NULL)   return; // nothing to remove

	if (*data > rec)
	{ 
		if (left != NULL) 
		{
			left->remove(rec);
			if (left->data == NULL)
			{
				delete left;
				left = NULL;
			}
		}
		return;
	}
	if (*data < rec)
	{ 
		if (right != NULL) 
		{
			right->remove(rec);
			if (right->data == NULL)
			{
				delete right;
				right = NULL;
			}
		}
		return;
	}
	// *data == rec 
	if (left == NULL && right == NULL)
	{
		delete data;
		data = NULL;
		return;
	}
	if  (left != NULL)
	{
		*data = left->max();
		left->remove(*data);
		if (left->data == NULL)
		{
			delete left;
			left = NULL;
		}
		return;
	}
	if  (right != NULL)
	{
		*data = right->min();
		right->remove(*data);
		if (right->data == NULL)
		{
			delete right;
			right = NULL;
		}
		return;
	}
	cout << "Error in removing";
} 



template<typename T>   
T BST<T>::searchdata(T rec)
{
	if (data == NULL) return rec;
	if (*data == rec)
       return *data;
    if (*data > rec) // try left;
	{
		if (left != NULL)	return left->searchdata(rec);
	}
    else  // try right;
	{
		if (right != NULL)	return right->searchdata(rec);
	}
	// cout << "Can't find:";
	return rec;
}


template<typename T>   
T BST<T>::max()
{
	if (right != NULL)	return right->max();
	return *data;
}


template<typename T>   
T BST<T>::min()
{
	if (left != NULL)	return left->min();
	return *data;
}



template<typename T>   
void BST<T>::print()
{
    if (data==NULL) return;
    if (left != NULL) left->print();
    data->print_me();
    if (right != NULL) right->print();
}


template<typename T>
BST<T>::~BST()     // Destructor
{
    if (left != NULL)   delete left;
    if (data != NULL)   delete data;
    if (right != NULL)	delete right;
}