#ifndef BST_H
#define BST_H

#include<iostream>

using namespace std;

template<class elemType>
struct node {
	elemType info;
	node<elemType> *leftLink;
	node<elemType> *rightLink;
};

template<class elemType>
class BST
{
public:
	BST();
	~BST();

	void insert(elemType &insertItem);
	bool search(elemType &searchItem);
	bool isEmpty();
	void inorderTraversal();
	void preorderTraversal();
	void postorderTraversal();
	void destroy(node<elemType> *point);
	elemType getMaxElem();
    void bstToFile(ofstream &file1);

private:
	void insert(elemType &item, node<elemType> *point);
	void inorderTraversal(node<elemType> *point);
	void preorderTraversal(node<elemType> *point);
	void postorderTraversal(node<elemType> *point);
	void bstToFile(node<elemType> *point, ofstream &f);

	node<elemType> *root;
};

template<class elemType>
BST<elemType>::BST() {
	root = NULL;
}

template<class elemType>
BST<elemType>::~BST() {
	destroy(root);
}

template<class elemType>
void BST<elemType>::insert(elemType &insertItem) {
	if(root == NULL)
	{
		root = new node<elemType>;
		root->info = insertItem;
		root->leftLink = NULL;
		root->rightLink = NULL;
	}
	else
	{
		insert(insertItem, root);
	}
}

template<class elemType>
bool BST<elemType>::search(elemType &searchItem) {
	node<elemType> *current;

	bool found = false;

	if(root == NULL)
	{
		cout << "Cannot search an empty tree." << endl;
	}
	else
	{
		current = root;
		while(current != NULL && found == false)
		{
			if(searchItem == current->info)
				found = true;

			else if(searchItem < current->info)
				current = current->leftLink;
			else
				current = current->rightLink;
		}
	}

	return found;
}


template<class elemType>
bool BST<elemType>:: isEmpty() {
	return (root == NULL);
}

template<class elemType>
void BST<elemType>::inorderTraversal() {
	inorderTraversal(root);
}


template<class elemType>
void BST<elemType>::preorderTraversal() {
	preorderTraversal(root);
}


template<class elemType>
void BST<elemType>::postorderTraversal() {
	postorderTraversal(root);
}


template<class elemType>
void BST<elemType>::destroy(node<elemType> *point) {
	if(point != NULL)
	{
		destroy(point->leftLink);
		destroy(point->rightLink);
		delete point;
		point = NULL;
	}
}


template<class elemType>
elemType BST<elemType>::getMaxElem() {
	elemType max;

	if(root == NULL)
	{
		cout << "Error: Tree is empty." << endl;
	}

	else
	{
		node<elemType> *current;
	    current = root;

	    while(current->rightLink != NULL)
	    {
		    current = current->rightLink;
	    }

	     max = current->info;
	}

	return max;
}

template<class elemType>
void BST<elemType>::bstToFile(ofstream &file1) {
	bstToFile(root, file1);
}

template<class elemType>
void BST<elemType>::insert(elemType &item, node<elemType> *point) {
	node<elemType> *newNode;
	newNode = new node<elemType>;
	newNode->info = item;
	newNode->leftLink = NULL;
	newNode->rightLink = NULL;

		if(item == point->info)
		{
			cout << "Duplicates elements are not allowed." << endl;
			return;
		}
		else
		{

			if(item < point->info)
			{
				if(point->leftLink != NULL)
				    insert(item, point->leftLink);
			    else
			     	point->leftLink = newNode;
			}
			else
			{
				if(point->rightLink != NULL)
					insert(item, point->rightLink);
				else
					point->rightLink = newNode;
		    }

	     }

}

template<class elemType>
void BST<elemType>::inorderTraversal(node<elemType> *point) {

	if(point != NULL)
	{
		inoderTraversal(point->leftLink);
		cout << point->info << " ";
		inorderTraversal(point->rightLink);
	}
}


template<class elemType>
void BST<elemType>::preorderTraversal(node<elemType> *point) {

	if(point != NULL)
	{
		cout << point->info << " ";
		inoderTraversal(point->leftLink);
		inorderTraversal(point->rightLink);
	}
}

template<class elemType>
void BST<elemType>::postorderTraversal(node<elemType> *point) {

	if(point != NULL)
	{
		inoderTraversal(point->leftLink);
		inorderTraversal(point->rightLink);
		cout << point->info << " ";
	}
}

template<class elemType>
void BST<elemType>::bstToFile(node<elemType> *point, ofstream &f) {
	if(point == NULL)
	{
		return;
	}

	bstToFile(point->leftLink, f);
	f << point->info;
	bstToFile(point->rightLink, f);
}


#endif