#pragma once

#include <optional>
#include <stack>

template<typename Key, typename Data>
class BinarySearchTree
{
private:
	struct node
	{
		Key key;
		Data data;
		node* left;
		node* right;

		node(const Key& k, const Data& d) : key(k), data(d), left(nullptr), right(nullptr)
		{

		}
	};

	node* root;
	size_t count;

	node** _find(const Key& key)
	{
		node** p = &root;

		while (*p != nullptr && (*p)->key != key)
		{
			p = (*p)->key < key ? &((*p)->right) : &((*p)->left);
		}

		return p;
	}

public:
	BinarySearchTree();

	std::optional<Data> find(const Key& key);

	void insert(const Key& key, const Data& data);

	~BinarySearchTree();
};

template<typename Key, typename Data>
BinarySearchTree<Key, Data>::BinarySearchTree() :root(nullptr), count(0)
{

}

template<typename Key, typename Data>
std::optional<Data> BinarySearchTree<Key, Data>::find(const Key& key)
{
	std::optional<Data> res = std::nullopt;

	node** p = _find(key);

	if (*p)
	{
		res = (*p)->data;
	}

	return res;
}

template<typename Key, typename Data>
void BinarySearchTree<Key, Data>::insert(const Key& key, const Data& data)
{
	node** p = _find(key);

	if (*p)
	{
		(*p)->data = data;
	}
	else
	{
		(*p) = new node(key, data);
	}
}

template<typename Key, typename Data>
BinarySearchTree<Key, Data>::~BinarySearchTree()
{
	std::stack<node*> s;

	s.push(root);

	while (s.size())
	{
		auto top = s.top();
		s.pop();

		if (top)
		{
			s.push(top->left);
			s.push(top->right);
			delete top;
		}
	}
}