#ifndef BST_H
#define BST_H

#include<string>
#include<exception>
#include<cassert>


template<class DataType>
struct Node
{
	Node();

	DataType Item;	//assumes a copy constructor has been written for a DataType
	Node* Left;
	Node* Right;
};

template<class DataType>
Node<DataType>::Node()
{
	Left = NULL;
	Right = NULL;
}

template<class DataType>
class BST
{
	typedef void(*FunctionType)(DataType& Item);

public:
	BST();
	~BST();
	bool IsEmpty();
	void Insert(const DataType& NewItem);
	void Delete(const DataType& SearchItem);
	bool Retrieve(const DataType& SearchItem, DataType& Result);
	void PreorderTraverse(FunctionType Visit);
	void InorderTraverse(FunctionType Visit);
	void PostorderTraverse(FunctionType Visit);
private:
	Node<DataType>* Root;
	void Destroy(Node<DataType>*& pNode); //called in the destructor
	void InsertItem(Node<DataType>*& pNode, const DataType& NewItem);
	void DeleteItem(Node<DataType>*& pNode, const DataType& SearchItem);
	void DeleteNodeItem(Node<DataType>*& pNode);
	void DeleteLeftMost(Node<DataType>*& pNode, DataType& Item);
	bool RetrieveItem(Node<DataType>* pNode, const DataType& SearchItem, DataType& Item);
	void Preorder(Node<DataType>* pNode, FunctionType Visit);
	void Inorder(Node<DataType>* pNode, FunctionType Visit);
	void Postorder(Node<DataType>* pNode, FunctionType Visit);
};

template<class DataType>
BST<DataType>::BST()
{
	Root = NULL;
}

template<class DataType>
BST<DataType>::~BST()
{
	Destroy(Root);
}

template<class DataType>
bool BST<DataType>::IsEmpty()
{
	return (Root == NULL);
}

template<class DataType>
void BST<DataType>::Insert(const DataType& NewItem)
{
	InsertItem(Root, NewItem);
}

template<class DataType>
void BST<DataType>::Delete(const DataType& SearchItem)
{
	DeleteItem(Root, SearchItem);
}

template<class DataType>
bool BST<DataType>::Retrieve(const DataType& SearchItem, DataType& Result)
{
	return RetrieveItem(Root, SearchItem, Result);
}

template<class DataType>
void BST<DataType>::PreorderTraverse(FunctionType Visit)
{
	Preorder(Root, Visit);
}

template<class DataType>
void BST<DataType>::InorderTraverse(FunctionType Visit)
{
	Inorder(Root, Visit);
}

template<class DataType>
void BST<DataType>::PostorderTraverse(FunctionType Visit)
{
	Postorder(Root, Visit);
}

template<class DataType>
void BST<DataType>::Destroy(Node<DataType>*& pNode) //called in the destructor
{
	if (pNode->Left != NULL)
	{
		Destroy(pNode->Left);
		pNode->Left = NULL;
	}
	if (pNode->Right != NULL)
	{
		Destroy(pNode->Right);
		pNode->Right = NULL;
	}
	if (pNode != NULL)
	{
		delete pNode;
		pNode = NULL;
	}
	else
	{
		assert(false);
	}

}

template<class DataType>
void BST<DataType>::InsertItem(Node<DataType>*& pNode, const DataType& NewItem)
{
	if (pNode == NULL)
	{
		pNode = new Node<DataType>();
		pNode->Item = NewItem;
	}
	else if (NewItem < pNode->Item)
	{
		InsertItem(pNode->Left, NewItem);
	}
	else if (NewItem > pNode->Item)
	{
		InsertItem(pNode->Right, NewItem);
	}

}

template<class DataType>
inline void BST<DataType>::DeleteItem(Node<DataType>*& pNode, const DataType & SearchItem)
{
}

template<class DataType>
inline void BST<DataType>::DeleteNodeItem(Node<DataType>*& pNode)
{
}

template<class DataType>
inline void BST<DataType>::DeleteLeftMost(Node<DataType>*& pNode, DataType & Item)
{
}

//operators == and > must be defined for DataType
template<class DataType>
bool BST<DataType>::RetrieveItem(Node<DataType>* pNode,
	const DataType& SearchItem,
	DataType& Item)
{
	bool result = false;
	if (pNode == NULL)
	{
		result = false;
	}
	else if (SearchItem == pNode->Item)
	{
		result = true;
		Item = pNode->Item;
	}
	else if (SearchItem > pNode->Item)
	{
		result = RetrieveItem(pNode->Right, SearchItem, Item);
	}
	else
	{
		result = RetrieveItem(pNode->Left, SearchItem, Item);
	}
	return result;
}

template<class DataType>
void BST<DataType>::Preorder(Node<DataType>* pNode, FunctionType Visit)
{
	if (pNode != NULL)
	{
		Visit(pNode->Item);
	}
	if (pNode->Left != NULL)
	{
		Preorder(pNode->Left, Visit);
	}
	if (pNode->Right != NULL)
	{
		Preorder(pNode->Right, Visit);
	}
}
template<class DataType>
void BST<DataType>::Inorder(Node<DataType>* pNode, FunctionType Visit)
{
	if (pNode->Left != NULL)
	{
		Inorder(pNode->Left, Visit);
	}
	if (pNode != NULL)
	{
		Visit(pNode->Item);
	}
	if (pNode->Right != NULL)
	{
		Inorder(pNode->Right, Visit);
	}
}

template<class DataType>
void BST<DataType>::Postorder(Node<DataType>* pNode, FunctionType Visit)
{
	if (pNode->Left != NULL)
	{
		Postorder(pNode->Left, Visit);
	}
	if (pNode->Right != NULL)
	{
		Postorder(pNode->Right, Visit);
	}
	if (pNode != NULL)
	{
		Visit(pNode->Item);
	}
}

#endif