#pragma once
#include <iostream>
#include <cstdlib>

using namespace std;

template <class T>
class BSTree {
	template <class T1>
	struct Node {
		T key;
		Node* left;
		Node* right;
	};

private:
	Node<T>* root; /// a root of node pointer
	void removeSubtree(Node<T>* ptr);
	Node<T>* createLeafPrivate(T key);
	void addLeafPrivate(T key, Node<T>* ptr);
	void addLeafPrivate(T key, Node<T>* ptr, int(*compareTwo)(const T& newData, const T& node)); //compare two objects with callback
	void findInOrderCallbackPrivate(Node<T>* ptr, void(*callback)(T & data));
	void traverse(int order, Node<T>* root);
	void removeNodePrivate(T key, Node<T>* ptr);
	void removeRootMatch();
	void removeMatch(Node<T>* parent, Node<T>* match, bool left);

public:
	BSTree();
	~BSTree();
	void addLeaf(T key);
	void addLeaf(T key, int(*compareTwo)(const T& newData, const T& node));
	void findInOrderCallback(void(*callback)(T & data));
	T returnRootKey();
	void removeNode(T key);
	void traverse(int order);
};

template<class T>
BSTree<T>::BSTree() {
	root = NULL;
}

template<class T>
BSTree<T>::~BSTree()
{
	//
}

template<class T>
void BSTree<T>::removeSubtree(Node<T> * ptr)
{
	if (root != NULL) {
		if (ptr->left != NULL) {
			removeSubtree(ptr->left);
		}
		if (ptr->right != NULL) {
			removeSubtree(ptr->right);
		}
		delete ptr;
	}
}

template<class T>
BSTree<T>::Node<T>* BSTree<T>::createLeafPrivate(T key) {
	Node<T>* n = new Node<T>;
	n->key = key;
	n->left = nullptr;
	n->right = nullptr;
	return n;
}

template<class T>
void BSTree<T>::addLeafPrivate(T key, Node<T>* ptr) {
	if (ptr == NULL)
		root = createLeafPrivate(key);
	else if (key < ptr->key) {
		if (ptr->left != 0) {
			addLeafPrivate(key, ptr->left);
		}
		else {
			ptr->left = createLeafPrivate(key);
		}
	}
	else if (key > ptr->key) {
		if (ptr->right != 0) {
			addLeafPrivate(key, ptr->right);
		}
		else {
			ptr->right = createLeafPrivate(key);
		}
	}
	else {
		cout << "The value " << key << " has already added to the tree";
	}
}

template<class T>
void BSTree<T>::addLeafPrivate(T key, Node<T>* ptr, int(*compareTwo)(const T &newData, const T &node))
{
	if (ptr == NULL) {
		root = createLeafPrivate(key);
	}
	else if (compareTwo(key, ptr->key) == -1) {
		if (ptr->left != NULL)
			addLeafPrivate(key, ptr->left, compareTwo);
		else
			ptr->left = createLeafPrivate(key);
	}
	else if (compareTwo(key, ptr->key) == 1) {
		if (ptr->right != NULL)
			addLeafPrivate(key, ptr->right, compareTwo);
		else
			ptr->right = createLeafPrivate(key);
	}
	else
		return;
}

template<class T>
void BSTree<T>::addLeaf(T key) {
	addLeafPrivate(key, root);
}

template<class T>
void BSTree<T>::addLeaf(T key, int(*compareTwo)(const T &newData, const T &node))
{
	addLeafPrivate(key, root, compareTwo);
}

template<class T>
void BSTree<T>::findInOrderCallback(void(*callback)(T & data)) {
	findInOrderPrivate(root, callback);
}

template<class T>
void BSTree<T>::findInOrderCallbackPrivate(Node<T>* ptr, void(*callback)(T & data)) {
	if (root != NULL) {
		if (ptr->left != 0) {
			findInOrderPrivate(ptr->left, callback);
		}
		callback(ptr->key);
		if (ptr->right != 0) {
			findInOrderPrivate(ptr->right, callback);
		}
	}
	else {
		cout << "The tree is empty";
	}
}

template<class T>
BSTree<T>::Node<T>* BSTree<T>::findNode(T key) {
	return findNodePrivate(key, root);
}

template<class T>
T BSTree<T>::returnRootKey()
{
	return root->key;
}

template<class T>
void BSTree<T>::traverse(int order)
{
	traverse(order, root);
}

template<class T>
void BSTree<T>::traverse(int order, Node<T>* ptr)
{
	if (order == 1)
		callback(ptr->key);
	if (ptr->left != NULL)
		traverse(order, ptr->left);
	if (order == 2)
		callback(ptr->key);
	if (ptr->right != NULL)
		traverse(order, ptr->right);
	if (order == 3)
		callback(ptr->key);
}

template<class T>
void BSTree<T>::removeNode(T key)
{
	removeNodePrivate(key, root);
}

template<class T>
void BSTree<T>::removeNodePrivate(T key, Node<T> * parent)
{
	if (root != NULL) {
		if (root->key == key) {
			removeRootMatch();
		}
		else {
			if (key < parent->key && parent->left != NULL) {
				parent->left->key == key ?
					removeMatch(parent, parent->left, true) :
					removeNodePrivate(key, parent->left);
			}
			else if (key > parent->key && parent->right != NULL) {
				parent->right->key == key ?
					removeMatch(parent, parent->right, false) :
					removeNodePrivate(key, parent->right);
			}
			else {
				cout << "The key " << key << " was not found in the tree.\n";
			}
		}
	}
	else {
		cout << "The tree is empty\n";
	}
}

template<class T>
void BSTree<T>::removeRootMatch()
{
	if (root != NULL) {
		Node<T>* delPtr = root;
		int smallestInRightSubtree;
		if (root->left == NULL && root->right == NULL) {
			root = NULL;
			delete delPtr;
		}
		else if (delPtr->left == NULL || delPtr->right == NULL) {
			root = delPtr->left;
			if (delPtr->right != NULL)
				root = delPtr->right;
			delete delPtr;
			cout << "The new root is" << root->key << endl;
		}
		else {
			smallestInRightSubtree = findSmallestPrivate(root->right);
			removeNodePrivate(smallestInRightSubtree, root);
			root->key = smallestInRightSubtree;
			cout << "The new root is" << root->key << endl;
		}
	}
	else {
		cout << "Cannot remove the root. The tree is empty";
	}
}

template<class T>
void BSTree<T>::removeMatch(Node<T> * parent, Node<T> * match, bool left)
{
	if (root != NULL) {
		Node<T>* delPtr;
		int matchKey = match->key;
		int smallestInRightSubtree;

		if (match->left == NULL && match->right == NULL) {
			delPtr = match;
			left == true ?
				parent->left = NULL :
				parent->right = NULL;
			delete delPtr;
			cout << "The Node containing key " << matchKey << " was removed";
		}
		else if (match->left == NULL || match->right == NULL) {
			if (match->right != NULL) {
				left == true ?
					parent->left = match->right :
					parent->right = match->right;
				match->right = NULL;
			}
			else {
				left == true ?
					parent->left = match->left :
					parent->right = match->left;
				match->left = NULL;
			}
			delPtr = match;
			delete match;
		}
		else {
			smallestInRightSubtree = findSmallestPrivate(match->right);
			removeNodePrivate(smallestInRightSubtree, match);
			match->key = smallestInRightSubtree;
		}
	}
	else {
		cout << "The tree is empty. Cannot remove the match";
	}
}