//Binary tree node abstract class
template <class Elem> class BinNode {
	public:
		virtual Elem& val() =0;
		virtual void setVal(const Elem& ) =0;
		virtual BinNode* left() const =0;
		virtual void setLeft(BinNode*) =0;
		virtual BinNode* right() const =0;
		virtual void setRight(BinNode*) =0;
		virtual bool isLeaf() =0;
};

//Binary tree node class
template <class Elem> 
class BinNodePtr : public BinNode<Elem> {
	private:
		Elem it;
		BinNodePtr* lc;
		BinNodePtr* rc;
	public:
		//Two constructors--with and without initial values
		BinNodePtr() { lc=rc=NULL; }
		BinNodePtr(Elem e,BinNodePtr* l=NULL,BinNodePtr* r=NULL)
		{ it=e; lc=l; rc=r; }
		~BinNodePtr() {}
		Elem& val() {return it;}
		void setVal(const Elem& e ) {it=e;}
		inline BinNode<Elem>* left() const { return lc; }
		void setLeft(BinNode<Elem>*b) { lc=(BinNodePtr*)b; }
		inline BinNode<Elem>* right() const { return rc; }
		void setRight(BinNode<Elem>*b) { rc=(BinNodePtr*)b; }
		bool isLeaf() {return (lc==NULL) && (rc==NULL); }
};


//Binary Search Tree implementation for the Dictionary ADT
template <class Elem>
class BST {
	private:
		BinNode<Elem>* root;          //Root of the BST
		int nodecount;            //Number of nodes in the BST
		//Elem* Array;
		//Private "helper" functions
		void clearhelp(BinNode<Elem>*);
		BinNode<Elem>* inserthelp(BinNode<Elem>*,const Elem&);
		//BinNode<Elem>* deletemin(BinNode<Elem>*,BinNode<Elem>*&);
		//BinNode<Elem>* removehelp(BinNode<Elem>*, const Elem&, BinNode<Elem>*&);
		void preorderhelp(BinNode<Elem>* ,int) const;
		void inorderhelp(BinNode<Elem>* ,int) const;
		void postorderhelp(BinNode<Elem>* ,int) const;
		int sizehelp(const BinNode<Elem>* ) const;
        void levelhelp(Elem ,BinNode<Elem>* ,int &,int);
		void searchhelp(Elem , BinNode<Elem> *&, BinNode<Elem>* );
		void biglevelhelp(BinNode<Elem>* ) ;
		//bool findhelp(BinNode<Elem>*, const Elem&, Elem&) const;
		void printhelp(BinNode<Elem>*, int) const;
	public:
		BST() {root=NULL; nodecount=0; }       //Constuctor
		~BST() {clearhelp(root); }             //Destructor
		void clear()
		{ clearhelp(root); root=NULL;nodecount=0; }
		bool insert(const Elem& e) {
			root=inserthelp(root,e);
			nodecount++;
			return true;
		}
		/*bool remove(const Elem& K,Elem& e) {
			BinNode<Elem>* t=NULL;
			root=removehelp(root,K,t);
			if(t==NULL) return false;  //Nothing found
			e=t->val();
			nodecount--;
			delete t;
			return true;
		}*/
		/*bool removeany(Elem& e) { //Delete min value
			if(root==NULL) return false;      //Empty tree
			BinNode<Elem>* t;
			root=deletemin(root,t);
			e=t->val();
			delete t;
			nodecount--;
			return true;
		}*/
		/*bool find(const Elem& K,Elem& e) const
		{ return findhelp(root,K,e); }*/
		int size(Elem key);
		void print() const {
			if (root==NULL) cout<<"The BST is empty.\n";
			else printhelp(root,0);
		}
		int level(Elem key);
		void biglevel() ;
		//int height(const BinNode<Elem>* ) const ;
		void preorder() const ;
		void inorder() const ;
		void postorder() const ;
};

/*
template <class Elem>
bool BST<Elem>::findhelp(BinNode<Elem>* subroot, const Elem& K, Elem& e) const {
	if (subroot==NULL) return false;            //Empty tree
	else if (K<subroot->val())
		return findhelp(subroot->left(),K,e);
	else if (K>subroot->val())
		return findhelp(subroot->right(),K,e);
	else { e=subroot->val(); return true; }           //Found it
}*/


template <class Elem>
BinNode<Elem>* BST<Elem>::inserthelp(BinNode<Elem>* subroot,const Elem& val) {
	if (subroot==NULL)           //Empty tree:creat node
		return (new BinNodePtr<Elem>(val, NULL, NULL));
	if (val<subroot->val())  //Insert on left
		subroot->setLeft(inserthelp(subroot->left(),val));
	else subroot->setRight(inserthelp(subroot->right(),val));
	return subroot;    //Return subtree with node inserted
}

/*
template <class Elem>
BinNode<Elem>* BST<Elem>::
deletemin(BinNode<Elem>* subroot,BinNode<Elem>*& min) {
	if(subroot->left()==NULL) {   //Found min
		min=subroot;
		return subroot->right();
	}
	else {
		subroot->setLeft(deletemin(subroot->left(),min));
		return subroot;
	}
}*/

/*
template <class Elem>
BinNode<Elem>* BST<Elem>::removehelp(BinNode<Elem>* subroot, const Elem& K, BinNode<Elem>*& t) {
	if (subroot==NULL) return NULL;   //Val is not in tree
	else if (KEComp::lt(K,subroot->val()))    //Check left
		subroot->setLeft(removehelp(subroot->left(),K,t));
	else if (KEComp::gt(K,subroot->val()))    //Check right
		subroot->setRight(removehelp(subroot->right(),K,t));
	else {                      //Found it:remove it
		BinNode<Elem>* temp;
		t=subroot;
		if (subroot->left()==NULL)       //Only a right child
			subroot=subroot->right();    //so point to right
		else if (subroot->right==NULL)   //Only a left child
			subroot=subroot->left();     //so point to left
		else {              //Both children are non-empty
			subroot->setRight(deletemin(subroot->right(),temp));
			Elem te=subroot->val();
			subroot->setVal(temp->val());
			temp->setVal(te);
			t=temp;
		}
	}
	return subroot;
}*/

template <class Elem>
void BST<Elem>::clearhelp(BinNode<Elem>* subroot) {
	if (subroot==NULL) return;
	clearhelp(subroot->left());
	clearhelp(subroot->right());
	delete subroot;
}

template <class Elem>
void BST<Elem>::printhelp(BinNode<Elem>* subroot, int level) const {
	if (subroot==NULL) return;               //Empty tree
	printhelp(subroot->left(), level+1);      //Do left subtree
	for (int i=0;i<level;i++)                //Indent to level
		cout << " ";
	cout << subroot->val() << "\n";    //Print node value
	printhelp(subroot->right(), level+1);    //Do right subtree
}


template <class Elem>
void BST<Elem>::levelhelp(Elem key,BinNode<Elem>* subroot,int &h,int lh)
{
  if(subroot==NULL) h=-1;
  else if(subroot->val()==key) h=lh;         //{searchnode=subroot;return;}
  else 
  { levelhelp(key,subroot->left(),h,lh+1);
    if(h==-1) levelhelp(key,subroot->right(),h,lh+1);
  }
}


template <class Elem>
int BST<Elem>::level(Elem key)
{
	int h;
	//BinNode<Elem> *searchnode;
	levelhelp(key,root,h,1);
	//int a=height(root);
	//int b=height(searchnode);
	return h;
}

template <class Elem>
void BST<Elem>::searchhelp(Elem key, BinNode<Elem> *&searchnode, BinNode<Elem>* subroot)
{
  if(subroot==NULL)return;
  if(subroot->val()==key) {searchnode=subroot;return;}
  else 
  { searchhelp(key,searchnode,subroot->left());
    searchhelp(key,searchnode,subroot->right());
  }
}
/*
void level(BTree *b, BTree *p, int &h, int lh)
{
	if(b==NULL) h=-1;                              //if the tree is empty, return 0
	else if (p==b) h=lh;                           //when node p is found
	else{
		level(b->left, p, h, lh+1);                //find in the left sub tree
		if(h==-1) level(b->right, p, h, lh+1);     //find in the right sub tree
	}
}
*/
/*
template <class Elem>
int BST<Elem>::height(const BinNode<Elem>* T) const 
{
	if(T==NULL) return 0;
	else return 1+Max(height(T->left()),height(T->right()));
}*/

template <class Elem>
Elem Max(const Elem u,const Elem v) {
	if (u>v) return u; else return v;
}

template <class Elem>
int BST<Elem>::sizehelp(const BinNode<Elem>* T) const {
	if(T==NULL) return 0;
	else return 1+sizehelp(T->left())+sizehelp(T->right());
}

template <class Elem>
int BST<Elem>::size(Elem key)
{
	BinNode<Elem> *searchnode;
	searchhelp(key,searchnode,root);
	return sizehelp(searchnode);
}

template <class Elem>
void BST<Elem>::preorderhelp(BinNode<Elem>* subroot,int i) const {
	//Array=new Elem[InitTreeSize];
	if (subroot==NULL) return;
	cout<< subroot->val() << " : " << i << "." <<endl;
	preorderhelp(subroot->left(),i+1);
	preorderhelp(subroot->right(),i+1);
}

template <class Elem>
void BST<Elem>::preorder() const {
	cout<< "Data is in preorder: \n";
	preorderhelp(root,1);
}

template <class Elem>
void BST<Elem>::biglevelhelp(BinNode<Elem>* subroot)  {
	if (subroot==NULL) return;
	cout<< subroot->val() << " level: " << level(subroot->val()) << ";" << endl
	    << "   length of path: " << level(subroot->val()) -1<< ";" <<endl
		<< "   number of descendants: " << size(subroot->val())-1 << ";" <<endl 
		<< "   number of ancestors: " << level(subroot->val())-1 << "." <<endl;
	biglevelhelp(subroot->left());
	biglevelhelp(subroot->right());
}


template <class Elem>
void BST<Elem>::biglevel() {
	biglevelhelp(root);
}


template <class Elem>
void BST<Elem>::inorderhelp(BinNode<Elem>* subroot,int i) const {
	if (subroot==NULL) return;
	inorderhelp(subroot->left(),i+1);
	cout<< subroot->val() << " : " << i << "." <<endl;
	inorderhelp(subroot->right(),i+1);
}

template <class Elem>
void BST<Elem>::inorder() const {
	cout<< "Data is in Inorder: \n";
	inorderhelp(root,1);
}


template <class Elem>
void BST<Elem>::postorderhelp(BinNode<Elem>* subroot,int i) const {
	if (subroot==NULL) return;
	postorderhelp(subroot->left(),i+1);
	postorderhelp(subroot->right(),i+1);
	cout<< subroot->val() << " : " << i << "." <<endl;
}

template <class Elem>
void BST<Elem>::postorder() const {
	cout<< "Data is in postorder: \n";
	postorderhelp(root,1);
}