#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_NODE
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_NODE

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2011 by Douglas Wilhelm Harder.  All rights reserved.

namespace Data_structures {
	template <typename Type>
	class Binary_node {
		protected:
			Type element;
			Binary_node *left_tree;
			Binary_node *right_tree;

		public:
			Binary_node( Type const & );

			Type retrieve() const;
			virtual Binary_node *left() const;
			virtual Binary_node *right() const;

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

			void clear();
	};

	template <typename Type>
	Binary_node<Type>::Binary_node( Type const &obj ):
	element( obj ),
	left_tree( 0 ),
	right_tree( 0 ) {
		// Empty constructor
	}

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

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

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

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

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

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

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

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

		delete this;
	}
}

#endif