#ifndef BINARY_SEARCH_NODE_RECURSIVE
#define BINARY_SEARCH_NODE_RECURSIVE

#ifndef nullptr
#define nullptr 0
#endif

#include <cassert>
#include "Exception.h"

template <typename Type>
class Binary_search_tree;

template <typename Type>
class Binary_search_node {
	private:
		Type element;
		Binary_search_node *left_tree;
		Binary_search_node *right_tree;

	public:
		Binary_search_node( Type const & );

		Type retrieve() const;
		Binary_search_node *left() const;
		Binary_search_node *right() const;

		bool is_leaf() const;
		int size() const;
		int height() const;

		Type front() const;
		Type back() const;
		bool find( Type const & ) const;

		void clear();
		bool insert( Type const & );
		bool erase( Type const &, Binary_search_node *& );
};

template <typename Type>
Binary_search_node<Type>::Binary_search_node( Type const &obj ):
element( obj ),
left_tree( nullptr ),
right_tree( nullptr ) {
}

template <typename Type>
Type Binary_search_node<Type>::retrieve() const {
	return element;
}

template <typename Type>
Binary_search_node<Type> *Binary_search_node<Type>::left() const {
	return left_tree;
}

template <typename Type>
Binary_search_node<Type> *Binary_search_node<Type>::right() const {
	return right_tree;
}

template <typename Type>
int Binary_search_node<Type>::size() const {
	return 1 + (
		(  left() == nullptr ) ? 0 :  left()->size()
	) + (
		( right() == nullptr ) ? 0 : right()->size()
	);
}

template <typename Type>
int Binary_search_node<Type>::height() const {
	if ( left() == nullptr ) {
		if ( right() == nullptr ) {
			return 0;
		} else {
			return 1 + right()->height();
		}
	} else {
		if ( right() == nullptr ) {
			return 1 + left()->height();
		} else {
			return 1 + std::max( left()->height(), right()->height() );
		}
	}
}

template <typename Type>
bool Binary_search_node<Type>::is_leaf() const {
	return ( left() == nullptr ) && ( right() == nullptr );
}

template <typename Type>
Type Binary_search_node<Type>::front() const {
	return left() == nullptr ? retrieve() : left()->front();
}

template <typename Type>
Type Binary_search_node<Type>::back() const {
	return right() == nullptr ? retrieve() : right()->front();
}

template <typename Type>
bool Binary_search_node<Type>::find( Type const &obj ) const {
	if ( obj == retrieve() ) {
		return true;
	}

	if ( obj < retrieve() ) {
		if ( left() == nullptr ) {
			return false;
		} else {
			return left()->find( obj );
		}
	} else {
		assert( obj > retrieve() );

		if ( right() == nullptr ) {
			return false;
		} else {
			return right()->find( obj );
		}
	}
}

template <typename Type>
void Binary_search_node<Type>::clear() {
	if ( left() != nullptr ) {
		left()->clear();
	}

	if ( right() != nullptr ) {
		right()->clear();
	}

	delete this;
}

template <typename Type>
bool Binary_search_node<Type>::insert( Type const &obj ) {
	if ( retrieve() == obj ) {
		return false;
	}

	if ( obj < retrieve() ) {
		if ( left() == nullptr ) {
			left_tree = new Binary_search_node( obj );
			return true;
		} else {
			return left()->insert( obj );
		}
	} else {
		if ( right() == nullptr ) {
			right_tree = new Binary_search_node( obj );
			return true;
		} else {
			return right()->insert( obj );
		}
	}
}

template <typename Type>
bool Binary_search_node<Type>::erase( Type const &obj, Binary_search_node *&ptr_to_this ) {
	if ( retrieve() == obj ) {
		if ( is_leaf() ) {
			ptr_to_this = nullptr;
			delete this;
		} else if ( left() == nullptr ) {
			ptr_to_this = right();
			delete this;
		} else if ( right() == nullptr ) {
			ptr_to_this = left();
			delete this;
		} else {
			element = right()->front();
			right()->erase( retrieve(), right_tree );
		}

		return true;
	}

	if ( obj < retrieve() ) {
		return ( left() == nullptr ) ? false : left()->erase( obj, left_tree );
	} else {
		return ( right() == nullptr ) ? false : right()->erase( obj, right_tree );
	}
}

#endif