#ifndef BINARY_SEARCH_TREE_RECURSIVE_NULL
#define BINARY_SEARCH_TREE_RECURSIVE_NULL

#ifndef nullptr
#define nullptr 0
#endif

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

template <typename Type>
class Binary_search_tree {
	private:
		Binary_search_node<Type> *root_node;
		Binary_search_node<Type> *root() const;

	public:
		Binary_search_tree();
		~Binary_search_tree();

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

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

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

template <typename Type>
Binary_search_tree<Type>::Binary_search_tree():
root_node( nullptr ) {
	// empty
}

template <typename Type>
Binary_search_tree<Type>::~Binary_search_tree() {
	root()->clear( root_node );
}

template <typename Type>
Binary_search_node<Type> *Binary_search_tree<Type>::root() const {
	return root_node;
}

template <typename Type>
bool Binary_search_tree<Type>::empty() const {
	return root()->empty();
}

template <typename Type>
int Binary_search_tree<Type>::size() const {
	return root()->size();
}

template <typename Type>
int Binary_search_tree<Type>::height() const {
	return root()->height();
}

template <typename Type>
Type Binary_search_tree<Type>::front() const {
	return root()->front();
}

template <typename Type>
Type Binary_search_tree<Type>::back() const {
	return root()->back();
}

template <typename Type>
bool Binary_search_tree<Type>::find( Type const &obj ) const {
	return root()->find( obj );
}

template <typename Type>
void Binary_search_tree<Type>::clear() {
	root()->clear( root_node );
}

template <typename Type>
bool Binary_search_tree<Type>::insert( Type const &obj ) {
	return root()->insert( obj, root_node );
}

template <typename Type>
bool Binary_search_tree<Type>::erase( Type const &obj ) {
	return root()->erase( obj, root_node );
}

#endif