#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 ) {
	// 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;
}

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

/*
 *  int height() const
 *
 *  The height of a leaf node is 0.
 *  Otherwise, the height of a tree is the maximum height of
 *  either sub-tree plus one.
 */

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

/*
 *  bool is_leaf() const
 *
 *  A node is a leaf node if both its sub-trees are empty.
 */

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

/*
 *  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 assigned 'nullptr', 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 {
	return left() == nullptr ? 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 assigned 'nullptr', 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 {
	return right() == nullptr ? retrieve() : right()->front();
}

template <typename Type>
bool Binary_search_node<Type>::find( Type const &obj ) const {
	if ( obj == retrieve() ) {
		return true;
	} else if ( obj < retrieve() ) {
		return ( left() == nullptr ) ? false : left()->find( obj );
	} else {
		return ( right() == nullptr ) ? false : 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 we find the object, then we have four cases:
	//   1.  This is a leaf node
	//   2.  This tree has only a right sub-tree
	//   3.  This tree has only a left sub-tree
	//   4.  This tree has two sub-trees
	// In the first three cases, we update the pointer pointing to this this node.
	// In the last case, we copy up the smallest element in the right sub-tree,
	// and then call erase on that element on the right sub-tree.

	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