#ifndef BST_H
#define BST_H
#include <string>

using namespace std;

template<typename T>
class BST
{
private:
	class Node
	{
	public:
		Node(const T element);
		T element;
		Node* left;
		Node* right;
	};
	Node* root;
	int nrOfNodes;

	bool insert(const T& element, Node*& node);
	bool contains(const T& element, Node*& node);
	string traverse(Node*& node);
	void destruct(Node* node);

	bool goLeft;
	bool remove(const T& element, Node*& node);
	void replaceLeft(Node* node);
	void replaceRight(Node* node);
public:
	BST();
	bool insert(const T& element);
	bool contains(const T& element);
	string traverse();
	bool remove(const T& element);
	~BST();
};

#endif

template<typename T>
BST<T>::Node::Node(const T element)
{
	this->element = element;
	left = nullptr;
	right = nullptr;
}

template<typename T>
BST<T>::BST()
{
	nrOfNodes = 0;
	goLeft = true;
	root = nullptr;
}

template<typename T>
BST<T>::~BST()
{
	destruct(root);
}

template<typename T>
void BST<T>::destruct(Node* node)
{
	if (node != nullptr)
	{
		destruct(node->left);
		destruct(node->right);
		delete node;
	}
}

template<typename T>
bool BST<T>::insert(const T& element)
{
	return insert(element, root);
}

template<typename T>
bool BST<T>::insert(const T& element, Node*& node)
{
	if (node == nullptr)
	{
		node = new Node(element);
		nrOfNodes++;
		return true;
	}
	else if (node->element == element)
	{
		return false;
	}
	else
	{
		if (element < node->element)
		{
			return insert(element, node->left);
		}
		else
		{
			return insert(element, node->right);
		}
	}
}

template<typename T>
bool BST<T>::contains(const T& element)
{
	return contains(element, root);
}

template<typename T>
bool BST<T>::contains(const T& element, Node*& node)
{
	if (node == nullptr)
	{
		return false;
	}
	else if (node->element == element)
	{
		return true;
	}
	else
	{
		if (element < node->element)
		{
			return contains(element, node->left);
		}
		else
		{
			return contains(element, node->right);
		}
	}
}

template<typename T>
string BST<T>::traverse()
{
	return traverse(root);
}

template<typename T>
string BST<T>::traverse(Node*& node)
{
	if (node != nullptr)
	{
		return traverse(node->left).append(node->element.toString().append(traverse(node->right)));
	}
}

template<typename T>
bool BST<T>::remove(const T& element)
{
	return remove(element, root);
}

template<typename T>
bool BST<T>::remove(const T& element, Node*& node)
{
	if (node == nullptr)
	{
		return false;
	}
	else if (node->element == element)
	{
		if (node->left == nullptr && node->right == nullptr)
		{
			delete node;
			node = nullptr;
		}
		else
		{
			if (node->right == nullptr)
			{
				node->element = node->left->element;
				delete node->left;
				node->left = nullptr;
			}
			else if (node->left == nullptr)
			{
				node->element = node->right->element;
				delete node->right;
				node->right = nullptr;
			}
			else
			{
				if (goLeft)
				{
					replaceLeft(node);
					goLeft = false;
				}
				else
				{
					replaceRight(node);
					goLeft = true;
				}
			}
		}
		nrOfNodes--;
		return true;
	}
	else
	{
		if (element < node->element)
		{
			return remove(element, node->left);
		}
		else
		{
			return remove(element, node->right);
		}
	}
}

template<typename T>
void BST<T>::replaceLeft(Node* node)
{
	Node* iterator = node->left;
	if (iterator->right != nullptr)
	{
		while (iterator->right->right != nullptr)
		{
			iterator = iterator->right;
		}
		if (iterator->right->left == nullptr)
		{
			node->element = iterator->right->element;
			delete iterator->right;
			iterator->right = nullptr;
		}
		else
		{
			node->element = iterator->right->element;
			Node* toDel = iterator->right;
			iterator->right = iterator->right->left;
			delete toDel;
		}
	}
	else
	{
		if (iterator->left != nullptr)
		{
			node->element = iterator->element;
			delete node->left;
			node->left = nullptr;
		}
		else
		{
			node->element = iterator->element;
			Node* toDel = iterator;
			node->left = iterator->left;
			delete node->left;
			node->left = nullptr;
		}
	}
}

template<typename T>
void BST<T>::replaceRight(Node* node)
{
	Node* iterator = node->right;
	if (iterator->left != nullptr)
	{
		while (iterator->left->left != nullptr)
		{
			iterator = iterator->left;
		}
		if (iterator->left->right == nullptr)
		{
			node->element = iterator->left->element;
			delete iterator->left;
			iterator->left = nullptr;
		}
		else
		{
			node->element = iterator->left->element;
			Node* toDel = iterator->left;
			iterator->left = iterator->left->right;
			delete toDel;
		}
	}
	else
	{
		if (iterator->right != nullptr)
		{
			node->element = iterator->element;
			delete node->right;
			node->right = nullptr;
		}
		else
		{
			node->element = iterator->element;
			Node* toDel = iterator;
			node->right = iterator->right;
			delete node->right;
			node->right = nullptr;
		}
	}
}