#include <memory>
#include "stdafx.h"

template<class T>struct NodeType;

template<class T>
struct NodeType {
	T key;
	std::shared_ptr<NodeType> left;
	std::shared_ptr<NodeType> right;
	NodeType(T);
};

template<class T>
NodeType<T>::NodeType(T myItem){
	key = myItem;
	left = nullptr; 
	right = nullptr; 
}

template<class T>
struct BTS {
	std::shared_ptr<NodeType<T>>root;
	BTS();
	
	bool insert(T);
	bool find(T x);
	bool erase(T x);
	NodeType<T>& min(void);
	NodeType<T>& max(void);
};

template<class T>
BTS<T>::BTS() : root(nullptr) {}

template<class T>
bool BTS<T>::insert(T val) 
{
	std::shared_ptr<NodeType<T>> temp = std::make_shared<NodeType<T>>(val);
	
	if (root == NULL)
	{
		root = temp;
		return true;
	}
	else
	{
		std::shared_ptr<NodeType<T>> current = root;
		std::shared_ptr<NodeType<T>> parent = root;

		current = (temp->key < current->key) ? (current->left) : (current->right);
		while (current != NULL)
		{
			parent = current;
			current = (temp->key < current->key) ? (current->left) : (current->right);
		}

		if (temp->key < parent->key)
		{
			parent->left = temp;
			return true;
		}
		else if (temp->key > parent->key) 
		{
			parent->right = temp;
			return true;
		}
		return false;
	}
}

template<class T>
bool BTS<T>::find(T val)
{
	if (root == NULL)
	{
		std::cout << "tree is empty, cannot find this value" << std::endl;
		return false;
	}
	else
	{
		std::shared_ptr<NodeType<T>> current = root;
		while (current != NULL)
		{
			if (current->key == val)
			{
				std::cout << "Found value: " + current->key << std::endl;
				return true;
			}
			current = (current->key > val) ? (current->left) : (current->right);
		}
		std::cout << "Cannot find this value:"<< std::endl;
		return false;
	}
}

template<class T>
bool BTS<T>::erase(T val)
{

	if (root == NULL)
	{
		return false;
	}
	else
	{
		std::shared_ptr<NodeType<T>> current = root;
		std::shared_ptr<NodeType<T>> parent = root;
		std::shared_ptr<NodeType<T>> parent = root;

		current = (val < current->key) ? (current->left) : (current->right);
		while (current != NULL)
		{
			if (current->key == val)
			{
				if (parent->right == current) {
					parent->right = current->left;
				}
				else
					parent->left = current->right;
				current.reset(); 
			}
			parent = current;
			current = (key < current->key) ? (current->left) : (current->right);
		}

		if (temp->key < parent->key)
		{
			parent->left = temp;
			return true;
		}
		else if (temp->key > parent->key)
		{
			parent->right = temp;
			return true;
		}
		return false;
	}
}

template<class T>
NodeType<T> & BTS<T>::min(void)
{
	std::shared_ptr<NodeType<T>> temp = root;

	if (root == NULL)
		throw ("sth wrong");
	else
	{
		while (temp->left != NULL)
		{
			temp = temp->left;
		}
		return *temp;
	}
}

template<class T>
NodeType<T> & BTS<T>::max(void)
{
	std::shared_ptr<NodeType<T>> temp = root;

	if (root == NULL)
		throw("is not elemnt in the tree"); 
	else
	{
		while (temp->right != NULL)
		{
			temp = temp->right;
		}
		std::cout << temp->key << std::endl;
		return *temp;
	}
}