#include "StdAfx.h"
#include "BST.h"

Node::Node(void)
{
	value = 0;
	left = NULL;
	right = NULL;
}

Node::Node(int value)
{
	this->value = value;
	left = NULL;
	right = NULL;
}

Node::~Node(void)
{
	delete left;
	delete right;
}

BST::BST(void)
{
	root = NULL;
}

BST::~BST(void)
{
	delete root;
}

void _insert(Node** root, Node* node)
{
	Node* aux = *root;

	if (!aux)
	{
		*root = node;
	}
	else if (node->value <= aux->value)
	{
		_insert(&aux->left, node);
	}
	else
	{
		_insert(&aux->right, node);
	}
}

void BST::Insert(Node* node)
{
	_insert(&root, node);
}

Node* _search(Node* root, int i)
{
	if (!root)
	{
		return NULL;
	}

	if (i < root->value)
	{
		return _search(root->left, i);
	}
	else if (i > root->value)
	{
		return _search(root->right, i);
	}
	else
	{
		return root;
	}
}

Node* BST::Search(int i)
{
	return _search(root, i);
}

void _delete(Node*& root)
{
	Node* aux = root;

	if (!aux->left)
	{
		root = root->right;
		delete aux;
	}
	else if (!aux->right)
	{
		root = root->left;
		delete aux;
	}
	else
	{
		aux = root->left;

		while (aux->right)
		{
			aux = aux->right;
		}

		root->value = aux->value;
		_delete(aux);
	}
}

void BST::Delete(int i)
{
	Node* node = Search(i);

	if (!node)
	{
		return;
	}

	_delete(node);
}