#pragma once

#include <string>

using namespace std;

template <class Item>
class BSNode
{
public:
	BSNode(Item data);
	BSNode(const BSNode<Item>& other);

	~BSNode();

	void insert(Item value);
	BSNode<Item>& operator=(const BSNode<Item>& other);

	bool isLeaf() const;
	Item getData() const;
	BSNode<Item>* getLeft() const;
	BSNode<Item>* getRight() const;

	bool search(Item val) const;

	int getHeight() const;
	int getDepth(const BSNode<Item>& root) const;

	void printNodes() const; //for question 1 part C

private:
	Item _data;
	BSNode<Item>* _left;
	BSNode<Item>* _right;

	int _count; //for question 1 part B
	int getCurrNodeDistFromInputNode(const BSNode* node) const; //auxiliary function for getDepth

};

template <class Item>
BSNode<Item>::BSNode(Item data)
{
	this->_data = data;
	this->_left = NULL;
	this->_right = NULL;
}

template <class Item>
BSNode<Item>::~BSNode()
{
	if (this->_left != NULL)
	{
		delete this->_left;
	}

	if (this->_right != NULL)
	{
		delete this->_right;
	}
}

template <class Item>
void BSNode<Item>::insert(Item value)
{
	if (this->_data > value)
	{
		if (this->_left != NULL)
		{
			this->_left->insert(value);
		}
		else
		{
			this->_left = new BSNode<Item>(value);
		}
	}
	else if (this->_data < value)
	{
		if (this->_right != NULL)
		{
			this->_right->insert(value);
		}
		else
		{
			this->_right = new BSNode<Item>(value);
		}
	}
}

template <class Item>
BSNode<Item>* BSNode<Item>::getRight() const
{
	return this->_right;
}

template <class Item>
BSNode<Item>* BSNode<Item>::getLeft() const
{
	return this->_left;
}

template <class Item>
Item BSNode<Item>::getData() const
{
	return this->_data;
}

template <class Item>
bool BSNode<Item>::isLeaf() const
{
	return (this->_left == NULL && this->_right == NULL);
}

template <class Item>
bool BSNode<Item>::search(Item val) const
{
	bool left = false;
	bool right = false;

	if (this->_data == val)
	{
		return true;
	}

	if (this->isLeaf())
	{
		return false;
	}

	if (this->_left != NULL && this->_data > val)
	{
		left = this->_left->search(val);
	}

	if (this->_right != NULL && this->_data < val)
	{
		right = this->_right->search(val);
	}

	return left || right;
}

template <class Item>
int BSNode<Item>::getHeight() const
{
	int left = 0;
	int right = 0;

	if (this->_left != NULL)
	{
		left = 1 + this->_left->getHeight();
	}

	if (this->_right != NULL)
	{
		right = this->_right->getHeight() + 1;
	}

	return (right > left ? right : left);
}

template <class Item>
int BSNode<Item>::getDepth(const BSNode<Item>& root) const
{
	if (this->_data == root._data)
	{
		return 0;
	}

	if (root._left != NULL && root._data > this->_data)
	{
		return this->getDepth(*(root._left)) + 1;
	}

	if (root._right != NULL && root._data < this->_data)
	{
		return this->getDepth(*(root._right)) + 1;
	}

	return 0;
}

template <class Item>
BSNode<Item>::BSNode(const BSNode<Item>& other)
{
	this->_data = other._data;

	if (other._left != NULL)
	{
		this->_left = new BSNode<Item>(*other._left);
	}
	else
	{
		this->_left = NULL;
	}

	if (other._right != NULL)
	{
		this->_right = new BSNode<Item>(*other._right);
	}
	else
	{
		this->_right = NULL;
	}
}

template <class Item>
BSNode<Item>& BSNode<Item>::operator=(const BSNode<Item>& other)
{
	this->_data = other._data;

	if (other._left != NULL)
	{
		this->_left = new BSNode<Item>(*(other._left));
	}

	if (other._right != NULL)
	{
		this->_right = new BSNode<Item>(*other._right);
	}

	return *this;
}