//************************STANDARD LIBRARY HEADERS*************************************
#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstring>
#include<map>
#include<bitset>
#include<functional>
#include<deque>
#include<cassert>
#include<ctime>
#include<cctype>
#include<cstdlib>
#include<cstddef>
#include<algorithm>
#include<iterator>
#include<utility>
#include<cmath>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<numeric>
#include<cstdio>
#include<iomanip>
#include<complex>
//*************************************************************



//*************************SYSTEM HEADERS*****************************
#include<unistd.h>
#include<pthread.h>
#include<signal.h>
#include<dirent.h>
#include<fcntl.h>
#include<errno.h>
#include<sys/ioctl.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<sys/wait.h>
//********************************************************************
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef list<int> LI;
typedef list<double> LD;
typedef deque<int> DI;
typedef deque<string> DS;
typedef deque<DS> DDS;
typedef stack<int> SI;
typedef stack<string> SS;
typedef map<int,string> MIS;
typedef map<string,int> MSI;
typedef map<int,int> MII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;
typedef pair<int,int> PII;
typedef set<int> STI;
typedef multiset<int>MSTI;
typedef long long LL;
#define PI 3.14159265358979323846264338327950288
#define I(x) x::iterator
template<typename T>
class BinarySearchTree
{
	public:
		BinarySearchTree();
		~BinarySearchTree();
		void insert(const T&);
		void inOrderTraversal();
		void clear();
	private:
		class node
		{
			public:
				node(const T& _key)
				{
					key=_key;
					left=0;
					right=0;
					parent=0;
				}

			private:
			T key;
			node* left;
			node* right;
			node* parent;
			friend class BinarySearchTree;
		};
		void clear(node*);
		node* createNode(const T&);
		void inOrderTraversal(const node*);
		node* m_root;
		bool m_isFlag; // To counter the problem of equals
};
template<typename T>
BinarySearchTree<T>::BinarySearchTree():m_root(0),m_isFlag(true)
{
}
template<typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
	clear(m_root);
	m_root=0;
}
template<typename T>
void BinarySearchTree<T>::insert(const T& _key)
{
	node* l_new_node=createNode(_key);
	node* current=m_root;
	node* temp=0;
	while(current!=0)
	{
		temp=current;
		if(current->key == _key)
		{
			if(m_isFlag)
			{
				current=current->left;
				m_isFlag=false;
			}
			else
			{
				current=current->right;
				m_isFlag=true;
			}
		}
		else if(current->key < _key)
		{
			current=current->right;
		}
		else
		{
			current=current->left;
		}
	}
	l_new_node->parent=temp;
	if(!temp)
	{
		m_root=l_new_node;
	}
	else
	{
		if(temp->key < _key)
		{
			temp->right=l_new_node;
		}
		else
		{
			temp->left=l_new_node;
		}
	}
}
template<typename T>
BinarySearchTree<T>::node* BinarySearchTree<T>::createNode(const T& _key) /*******************This part is giving the error****************/
{
	return new node(_key);
}
template<typename T>
void BinarySearchTree<T>::inOrderTraversal()
{
	inOrderTraversal(m_root);
}
template<typename T>
void BinarySearchTree<T>::inOrderTraversal(const node* head)
{
	if(head==0)
	{
		return;
	}
	inOrderTraversal(head->left);
	cout<<head->key<<endl;
	inOrderTraversal(head->right);
}
template<typename T>
void BinarySearchTree<T>::clear(node* head)
{
	if(head==0)
	{
		return;
	}
	clear(head->left);
	clear(head->right);
	delete head;
}
template<typename T>
void BinarySearchTree<T>::clear()
{
	clear(m_root);
}
int main()
{
	BinarySearchTree<int> tree1;
	tree1.insert(5);
	tree1.insert(4);
	tree1.insert(17);
	tree1.insert(10);
	tree1.insert(7);
	tree1.insert(6);
	tree1.insert(2);
	tree1.insert(0);
	tree1.insert(9);
	tree1.inOrderTraversal();
	return 0;
}

template<typename T>
typename BinarySearchTree<T>::node* BinarySearchTree<T>::createNode(const T& _key) 
{
	return new node(_key);
}