#ifndef BINARY_SEARCH_NODE_RECURSIVE_NULL
#define BINARY_SEARCH_NODE_RECURSIVE_NULL

#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 empty() 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 &, Binary_search_node *& );
		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>
bool Binary_search_node<Type>::empty() const {
	return ( this == nullptr );
}

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

template <typename Type>
int Binary_search_node<Type>::height() const {
	return empty() ? -1 : 1 + std::max( left()->height(), right()->height() );
}

template <typename Type>
bool Binary_search_node<Type>::is_leaf() const {
	return ( !empty() && left()->empty() && right()->empty() );
}

template <typename Type>
Type Binary_search_node<Type>::front() const {
	if ( empty() ) {
		throw underflow();
	}

	return left()->empty() ? retrieve() : left()->front();
}

template <typename Type>
Type Binary_search_node<Type>::back() const {
	if ( empty() ) {
		throw underflow();
	}

	return right()->empty() ? retrieve() : right()->back();
}

template <typename Type>
bool Binary_search_node<Type>::find( Type const &obj ) const {
	if ( empty() ) {
		return false;
	}

	if ( obj == retrieve() ) {
		return true;
	}

	return ( obj < retrieve() ) ? left()->find( obj ) : right()->find( obj );
}

template <typename Type>
void Binary_search_node<Type>::clear() {
	if ( empty() ) {
		return;
	}

	left()->clear();
	right()->clear();

	delete this;
}

template <typename Type>
bool Binary_search_node<Type>::insert( Type const &obj, Binary_search_node *&ptr_to_this ) {
	if ( empty() ) {
		ptr_to_this = new Binary_search_node( obj );
		return true;
	}

	if ( retrieve() == obj ) {
		return false;
	}

	if ( obj < retrieve() ) {
		return left()->insert( obj, left_tree );
	} else {
		return right()->insert( obj, right_tree );
	}
}

template <typename Type>
bool Binary_search_node<Type>::erase( Type const &obj, Binary_search_node *&ptr_to_this ) {
	if ( empty() ) {
		return false;
	}

	if ( retrieve() == obj ) {
		if ( is_leaf() ) {
			ptr_to_this = nullptr;
			delete this;
		} else if ( left()->empty() ) {
			ptr_to_this = right();
			delete this;
		} else if ( right()->empty() ) {
			ptr_to_this = left();
			delete this;
		} else {
			element = right()->front();
			right()->erase( retrieve(), right_tree );
		}

		return true;
	}

	if ( obj < retrieve() ) {
		return left()->erase( obj, left_tree );
	} else {
		return right()->erase( obj, right_tree );
	}
}

#endif