//brian jahns
//cs252 1999
//binary search tree .cc file

#include <assert.h>
#include "Bintree.h"
#include "BST.h"


//default constructor
template <class T>
BST<T>::BST() : BinTree<T>() {}


//copy constructor
template <class T>
BST<T>::BST(const BST<T>& bst) : BinTree<T>(bst) {}


//destructor
template <class T>
BST<T>::~BST(){
DelTree(root);
}


//wrapper for Insert function
template <class T>
bool BST<T>::Insert(const T& item){
return true;//InsertHelper(item, root);
}


//wrapper for Delete function
template <class T>
bool BST<T>::Delete(const T& item){
return DeleteHelper(root, item);
}


//wrapper for Find function
template <class T>
bool BST<T>::Find(const T& item) const {
return FindHelper(item, root);
}


//finds a node and implicitly returns a value given the root of a tree
template <class T>
bool BST<T>::FindHelper(const T& item, Bnode<T>* node) const {
if (node == 0)
return false;
else if (item == node->data)
return true;
else if (item < node->data)
return FindHelper(item, node->lchild);
else
return FindHelper(item, node->rchild);
}


/*//inserts a node into a tree given the root node
template <class T>
bool BST<T>::InsertHelper(const T& item, Bnode<T>*& node){
if (node == 0){
node = new Bnode<T>(item, 0, 0);
assert(node != 0);
return true;
}
else if (node->data == item){
node->data.AddData(item);
return true;
}
else if (item < node->data)
return InsertHelper(item, node->lchild);
else
return InsertHelper(item, node->rchild);
}
*/


//finds node to be deleted
template <class T>
bool BST<T>::DeleteHelper(Bnode<T>*& node, const T& item){
if (node == 0)
return false;
if (item == node->data)
return DeleteItem(node);
else if (item < node->data)
return DeleteHelper(node->lchild, item);
else
return DeleteHelper(node->rchild, item);
}


//deletes a given node and relinks its children accordingly
template <class T>
bool BST<T>::DeleteItem(Bnode<T>*& node){
Bnode<T>* cur;
if (node->lchild == 0 && node->rchild == 0){
delete node;
node = 0;
}
else if (node->rchild == 0){
cur = node;
node = node->lchild;
cur->lchild = 0;
delete cur;
cur = 0;
}
else if (node->lchild == 0){
cur = node;
node = node->rchild;
cur->rchild = 0;
delete cur;
cur = 0;
}
else{
T item;
FindMinRST(node->rchild, item);
node->data = item;
}
return true;
}


//replaces the value of the given node with the minimum value of that node's
//right subtree
template <class T>
void BST<T>::FindMinRST(Bnode<T>*& node, T& sub){
if (node->lchild == 0){
sub = node->data;
Bnode<T>* cur = node;
node = node->rchild;
cur->rchild = 0;
delete cur;
cur = 0;
}
else
FindMinRST(node->lchild, sub);
}