#ifndef TREE_H
#define TREE_H

template <class T>
class Tree
{
	struct Node
	{
		T element;
		Node* left;
		Node* right;
	};

public:
	Tree();
	~Tree();            

	Node* main_root;

	void preorder(Node* current );
	void Insert( T value, Node* main_root );
	void Insert( T value );

	void Remove( T value );

	void Print();

	void PreorderPrint();

	void inOrderPrint(Node* current);
	void inOrderPrint();

	void PostOrderPrint();

	void Clear(Node* main_root);

};
#endif

template <class T>  
Tree<T>::Tree()
{
	main_root = 0;
	
}
template <class T>  
Tree<T>::~Tree()
{

}
template <class T> 
void Tree<T>::Insert( T value, Node* current )
{

	if(!main_root)
	{
		Node* n = new Node;

		n->element = value;

		n->left = 0;

		n->right = 0;

		main_root = n;
	}else if(value < current->element)
	{
		if( current->left != 0 )
		{
			Insert(value, current->left);
		}
		else
		{

			Node* n = new Node;

			n->element = value;

			n->left = 0;

			n->right = 0; 

			current->left = n; 

		}  
	}else if(value >= current->element)
	{
		if(current->right != 0)
		{
			Insert(value, current->right);
		}
		else
		{
			Node* n = new Node;

			n->element = value;

			n->left = 0;

			n->right = 0; 

			current->right = n;
		}
	}
}

template <class T>
void Tree<T>::Insert( T value )
{
	
	Insert(value , main_root);
}

template <class T>
void Tree<T>::Remove( T value )
{

}

template <class T> 
void Tree<T>::inOrderPrint(Node* main_root) 
{

	if (main_root != 0) 
	{
		inOrderPrint(main_root->left);  // print left subtree
		cout << main_root->element << " "; // print this node
		inOrderPrint(main_root->right); // print right subtree
	}
}

template <class T>
void Tree<T>::inOrderPrint()
{
	inOrderPrint( main_root );
}

template <class T> 
void Tree<T>::PostOrderPrint()
{

}

template <class T> 
void Tree<T>::Clear(Node* main_root)
{
	if(main_root!=0)
	{
		Clear(main_root->left);
		Clear(main_root->right);
		delete main_root;
	}

}