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

template<class T>struct Node;

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

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

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

template<class T>
bool BST<T>::insert(T val) 
{
	
}

template<class T>
bool BST<T>::find(T val)
{
	if (root == NULL)
	{
		std::cout << "tree is empty, cannot find this value" << std::endl;
		return false;
	}
	else
	{
		std::shared_ptr<Node<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 BST<T>::erase(T val)
{

}

template<class T>
Node<T> & BST<T>::min(void)
{
	
}

template<class T>
Node<T> & BST<T>::max(void)
{
	
}