#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;
typedef int datatype;
datatype max(datatype, datatype);
void is_bst(struct TreeNode* tree, int flag);

struct TreeNode{
	datatype item;
	TreeNode *left;
	TreeNode *right;
};


class TreeType{
	public:
		TreeType();
		TreeType(TreeType &orig); //Copy Constructor
		TreeType& operator =(TreeType& rhs);
		void InsertItem(datatype item);
		void Print_Tree();
		//int  TreeHeight();
		void DestroyTree();
		void DeleteItem(datatype item);
			
	private:
		TreeNode* root;
		void Insert(TreeNode* &root, datatype item);
		void Print(TreeNode* cur);
		//int  Height(TreeNode* root);
		void Delete(TreeNode* &tree, datatype item);
		void DeleteNode(TreeNode* &tree);
		void Destroy(TreeNode* root);
		void GetPredecessor(TreeNode* tree, datatype& data);
		void Copy(TreeNode* orig_ptr, TreeNode* &copy_ptr);
			
};

TreeType::TreeType(){
	root = NULL;
}

TreeType::TreeType(TreeType &orig){
	Copy(orig.root,root);
}

TreeType& TreeType::operator =(TreeType& rhs){
	if(this == &rhs) return *this;
	else{
		Destroy(root);
		Copy(rhs.root, root);
	}
	return *this;
}


void TreeType::InsertItem(datatype item){
	Insert(root,item);
}

void TreeType::Insert(TreeNode* &tree, datatype item){
	if(tree==NULL){
		tree=new TreeNode;
		tree->right = NULL;
		tree->left = NULL;
		tree->item = item;
	}
	else if(item<=tree->item) Insert(tree->left,item);
	else Insert(tree->right,item);
}

/*
int TreeType::TreeHeight(){
	return Height(root);
}
*/

void TreeType::DestroyTree(){
	Destroy(root);
	root=NULL;
}

void TreeType::Destroy(TreeNode* tree){
	if(tree != NULL){
		Destroy(tree->left);
		Destroy(tree->right);
		delete tree;
	}
}


void TreeType::Print(TreeNode* cur){
	if(cur !=NULL){
		Print(cur->left);
		cout<<cur->item<<endl;
		Print(cur->right);
	}
}

void TreeType::Print_Tree(){
	Print(root);
}

void TreeType::DeleteItem(datatype item){
	Delete(root,item);
}

void TreeType::Delete(TreeNode* &tree, datatype item){
	if(tree==NULL){
		cout<<"Item not found\n";
		return ;
	}
	else if(item<tree->item) Delete(tree->left,item);
	else if(item>tree->item) Delete(tree->right,item);
	else DeleteNode(tree);
}

void TreeType::DeleteNode(TreeNode* &tree){
	datatype data;
	TreeNode *temp;

	temp = tree;
	if(tree->left == NULL){
		tree = tree->right;
		delete temp;
	}
	else if(tree->right == NULL){
		tree=tree->left;
		delete temp;
	}
	else{
		GetPredecessor(tree->left, data);
		tree->item = data;
		Delete(tree->left, data);
	}
}

void TreeType::GetPredecessor(TreeNode* tree,datatype& data){
	while(tree->right != NULL) tree = tree->right;
	data = tree->item;
}

void TreeType::Copy(TreeNode* orig_ptr, TreeNode* &copy_ptr){
	if(orig_ptr == NULL) copy_ptr = NULL;
	else{
		copy_ptr = new TreeNode;
		copy_ptr->item = orig_ptr->item;
		Copy(orig_ptr->left, copy_ptr->left);
		Copy(orig_ptr->right, copy_ptr->right);
	}
}


datatype max(datatype x, datatype y){
	return x>y?x:y;
}

void is_bst(TreeNode* tree, int flag){
	if(tree == NULL) flag=1;
	else if(tree->left == NULL && tree->right == NULL)
		flag=1;
	else if(tree->left == NULL){
		if(tree->item < tree->right->item)
			is_bst(tree->right,flag);
		else flag=0;
	}
	else if(tree->right == NULL){
		if(tree->item > tree->left->item)
			is_bst(tree->right,flag);
		else flag=0;
	}
	else if(tree->right->item > tree->item 
		&& tree->left->item < tree->item){
			is_bst(tree->left,flag);
			if(flag!=0)is_bst(tree->right,flag);
	}
	else flag =0;
}

int main(){
	typedef int datatype;
	TreeType t,t1;
	int item;
	int sum=0;
	
	for(int i=1;i<=10;++i){
		item= i;
		t.InsertItem(item);
	}
	
	t.Print_Tree();
	cout<<endl;
	t.DeleteItem(6);
	TreeType t2=t; // Testing copy constructor
	t1=t;	//Testing overloaded = operator
	t1.Print_Tree();
	cout<<endl<<endl;
	
	TreeType ob1, ob2, ob3;
	ob1=ob2=ob3=t;
	ob1.Print_Tree(); //Testing cascaded assignment
	return 0;
}