#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( Binary_search_node *& );
		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 ) {
	// empty
}

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

/*
 *  Binary_search_node *left() const
 *  Binary_search_node *right() const
 *
 *  Returns the addresses of the left and right sub-trees, respectively.
 */

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;
}

/*
 *  bool empty() const
 *
 *  A node is empty if 'this' is assigned 'nullptr'.
 *
 *   - That is, empty() was called on a variable assigned the value 'nullptr'.
 */

template <typename Type>
bool Binary_search_node<Type>::empty() const {
	return ( this == nullptr );
}

/*
 *  int size() const
 *
 *  The size of an empty sub-tree is 0,
 *  Otherwise, the size is one plus the sum of the sizes of the two sub-trees.
 */

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

/*
 *  int height() const
 *
 *  The height of an empty sub-tree is -1,
 *  Otherwise, the height is one plus the maximum heights of the two sub-trees.
 */

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

/*
 *  bool is_leaf() const
 *
 *  A node is a leaf node if:
 *    - The node itself is not empty, and
 *    - Both left and right sub-trees are empty.
 */

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

/*
 *  Type front() const
 *
 *  The front is defined as that element that precedes all other elements in the
 *  tree (i.e., the first element).  This value is stored in the left-most node.
 *
 *  It is an undefined operation to call 'front' on an empty tree.
 *
 *  If the left sub-tree is empty, this node stores the first element,
 *  Otherwise, the first element of this sub-tree is the first element of
 *  the left sub-tree.
 */

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

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

/*
 *  Type back() const
 *
 *  The back is defined as that element that succeeds all other elements in the
 *  tree (i.e., the last element).  This value is stored in the right-most node.
 *
 *  It is an undefined operation to call 'back' on an empty tree.
 *
 *  If the right sub-tree is empty, this node stores the last element,
 *  Otherwise, the last element of this sub-tree is the last element of
 *  the right sub-tree.
 */

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( Binary_search_node *&ptr_to_this ) {
	if ( empty() ) {
		return;
	}

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

	delete this;

	ptr_to_this = nullptr;
}

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