#include<iostream>
#include <vector>
#include<queue>

template<typename T>
struct Node
{
	T info;
	Node<T> *left, *right, *parent;
	Node(const T c_info = T())
	{
		info = c_info;
		left = NULL;
		right = NULL;
		parent = NULL;
	}
};

template<typename T>
class BinaryTree
{
private:
	void RSD(Node<T> *aux) const
	{
		if (aux != NULL)
		{
			std::cout << aux->info << " ";
			RSD(aux->left);
			RSD(aux->right);
		}

	}
	void SDR(Node<T> *aux) const
	{
		if (aux != NULL)
		{
			SDR(aux->left);
			SDR(aux->right);
			std::cout << aux->info << " ";
		}
	}
	void SRD(Node<T> *aux) const
	{
		if (aux != NULL)
		{
			SRD(aux->left);
			std::cout << aux->info << " ";
			SRD(aux->right);
		}
	}
	void levels() const
	{
		std::queue<Node<T> *> c;
		for (c.push(root); c.empty() == false; c.pop())
		{
			std::cout << c.front()->info << " ";
			if (c.front()->left != NULL)
				c.push(c.front()->left);
			if (c.front()->right != NULL)
				c.push(c.front()->right);
		}
	}
	void postDelete(Node<T> *node)
	{
		if (node != NULL)
		{
			postDelete(node->left);
			postDelete(node->right);
			delete node;
		}
	}
	void transplant(Node<T>* node1, Node<T>* node2)
	{
		if (node1 == root)
			root = node2;
		else
			if (node1 == node1->parent->left)
				node1->parent->left = node2;
			else
				node1->parent->right = node2;
		if (node2 != NULL)
			node2->parent = node1->parent;
	}
public:
	Node<T> *root;
	void insert(const T &key)
	{
		if (root == NULL)
			root = new Node<T>(key);
		else
		{
			Node<T>* toInsert = new Node<T>(key);
			Node<T>* copyR = root;
			while (copyR)
			{
				if (toInsert->info > copyR->info)
				{
					if (copyR->right == NULL)
					{
						copyR->right = toInsert;
						toInsert->parent = copyR;
						return;
					}
					copyR = copyR->right;
				}
				else
				{
					if (copyR->left == NULL)
					{
						copyR->left = toInsert;
						toInsert->parent = copyR;
						return;
					}
					copyR = copyR->left;
				}
			}
		}
	}
	Node<T>* min(Node<T> *R) const
	{
		Node<T> *copyR = R;
		while (copyR->left != NULL)
			copyR = copyR->left;
		return copyR;
	}
	Node<T>* max(Node<T> *R) const
	{
		Node<T> *copyR = R;
		while (copyR->right != NULL)
			copyR = copyR->right;
		return copyR;
	}
	Node<T>* successor(Node<T> *node) const
	{
		if (node->right != NULL)
		{
			return min(node->right);
		}
		Node<T> *aux = node;
		while (aux->right == node && aux != NULL)
		{
			node = aux;
			aux = aux->parent;
		}
		aux = node->parent;
		return aux;
	}
	Node<T>* predecessor(Node<T> *node) const
	{
		if (node->left != NULL)
		{
			return max(node->left);
		}
		Node<T> *aux = node;
		while (aux->left == node && aux != NULL)
		{
			node = aux;
			aux = aux->parent;
		}
		aux = node->parent;
		return aux;
	}
	Node<T>* search(const T &val) const
	{
		Node<T> *aux = root;
		while (aux != NULL && aux->info != val)
		{
			if (val < aux->info)
				aux = aux->left;
			else
				aux = aux->right;
		}
		return aux;
	}
	void deleteNode(Node<T> *node)
	{
		if (node->left == NULL)
			transplant(node, node->right);
		else
			if (node->right == NULL)
				transplant(node, node->left);
			else
			{
				Node<T>* succ = successor(node);
				if (succ != node->right)
				{
					transplant(succ, succ->right);
					succ->right = node->right;
					node->right->parent = succ;
				}
				transplant(node, succ);
				succ->left = node->left;
				node->left->parent = succ;
			}
	}
	void clear()
	{
		postDelete(root);
		root = NULL;
	}
	void construct(const std::vector<T> elements)
	{
		for (auto element : elements)
			insert(element);
	}
	void printTree(const int &option) const
	{
		if (option == 1)
			RSD(root);
		else if (option == 2)
			SRD(root);
		else if (option == 3)
			SDR(root);
		else if (option == 4)
			levels();
	}
	BinaryTree()
	{
		root = NULL;
	}
	~BinaryTree()
	{
		clear();
	}
};

int main()
{

	BinaryTree<int> tree;
	Node<int> *node;
	int input, key;
	while (true)
	{
		std::cout << "1. Insert\n2. Max\n3. Min\n4. Successor\n5. Predeccessor\n6. Delete\n7. Empty\n8. Print tree\n9. Quit\n\n";
		std::cout << "Select option: ";
		std::cin >> input;
		switch (input)
		{
		case 1:
			std::cout << "Insert key: ";
			std::cin >> key;
			tree.insert(key);
			break;
		case 2:
			std::cin >> key;
			node = tree.search(key);
			if (node != NULL)
				std::cout << tree.max(node)->info << std::endl;
			else
				std::cout << "Invalid" << std::endl;
			break;
		case 3:
			std::cin >> key;
			node = tree.search(key);
			if (node != NULL)
				std::cout << tree.min(node)->info << std::endl;
			else
				std::cout << "Invalid" << std::endl;
			break;
		case 4:
			std::cin >> key;
			node = tree.search(key);
			if (node != NULL)
				std::cout << tree.successor(node)->info << std::endl;
			else
				std::cout << "Invalid" << std::endl;
			break;
		case 5:
			std::cin >> key;
			node = tree.search(key);
			if (node != NULL)
				std::cout << tree.predecessor(node)->info << std::endl;
			else
				std::cout << "Invalid" << std::endl;
			break;
		case 6:
			std::cin >> key;
			node = tree.search(key);
			if (node != NULL)
				tree.deleteNode(node);
			else
				std::cout << "Invalid" << std::endl;
			break;
		case 7:
			tree.clear();
			break;
		case 8:
			std::cin >> key;
			tree.printTree(key);
			std::cout << "\n";
			break;
		case 9:
			return 1;
			break;
		default:
			std::cout << "Invalid option.\n";
			break;
		}
		system("pause");
		system("cls");
	}
	return 0;
}