#include <iostream>
#include <queue>
using namespace std;
 
typedef struct node{
	node *left = nullptr;
	node *right = nullptr;
	int value;
}node;
 
class tree{
	public:
	node *root;
	tree(int val);
 
	void traverse();
 
	void level_traverse();
 
	void insertNode(int val);
 
	void deleteNode(int val);
 
	int find_maximum();
 
	int find_minimum();
 
	private:
	void p_preorder_traverse(node *n);
 
	void p_inorder_traverse(node *n);
 
	void p_postorder_traverse(node *n);
 
	void p_insert(node *n, int val);
 
	node* p_delete(node *n, int val);
 
	node* p_find_maximum(node* ref);
 
	node* p_find_minimum(node* ref);
 
	node* p_search(node *n, int val);
};
 
void tree::traverse(){
		printf("\n");
		p_preorder_traverse(this->root);
		printf("\n");
		p_inorder_traverse(this->root);
		printf("\n");
		p_postorder_traverse(this->root);
		printf("\n");
	}
 
void tree::insertNode(int val){
		p_insert(this->root, val);
	}
 
void tree::deleteNode(int val){
	p_delete(this->root, val);
}
 
tree::tree(int val){
		node *temp;
		temp = (node*)calloc(1,sizeof(node));
		temp->left = nullptr;
		temp->right = nullptr;
		temp->value = val;
		this->root = temp;
	}
 
int tree::find_maximum(){
	node* temp_n = p_find_maximum(this->root);
	return temp_n->value;
}
 
int tree::find_minimum(){
	node* temp_n = p_find_minimum(this->root);
	return temp_n->value;
}
 
void tree::level_traverse(){
	queue<node*> q_n;
	node* n;
	n= this->root;
	q_n.push(n);
	printf("\n");
	while(!q_n.empty()){
		printf("%d ", q_n.front()->value);
		n = q_n.front();
		q_n.pop();
		if(n->left!=nullptr){
			q_n.push(n->left);
			}
		if(n->right!=nullptr){
			q_n.push(n->right);
			};
	}
	printf("\n");
	return;
}
 
void tree::p_preorder_traverse(node *n){
		printf("%d ",n->value);
		if(n->left!=nullptr){p_preorder_traverse(n->left);}
		if(n->right!=nullptr){p_preorder_traverse(n->right);}
	};
 
void tree::p_inorder_traverse(node *n){
		if(n->left!=nullptr){p_inorder_traverse(n->left);}
		printf("%d ",n->value);
		if(n->right!=nullptr){p_inorder_traverse(n->right);}
	};
 
void tree::p_postorder_traverse(node *n){
		if(n->left!=nullptr){p_postorder_traverse(n->left);}
		if(n->right!=nullptr){p_postorder_traverse(n->right);}
		printf("%d ",n->value);
	};
 
void tree::p_insert(node *n, int val){
		node *temp;
		temp = (node*)calloc(1,sizeof(node));
		temp->value = val;
		if(n->value == temp->value)
		{
			printf("canceled. n->value : %d  val : %d. \n",n->value,val);
			return;
		}
		else if(n->value > temp->value)
		{
			if(n->left==nullptr){
				n->left = temp;
				printf("%d inserted in the left of %d.\n",temp->value,n->value);
				return;
 
			}
			else{p_insert(n->left,val);}
 
 
		}
		else if(n->value < temp->value)
		{
		if(n->right==nullptr){
				n->right = temp;
				printf("%d inserted in the right of %d.\n",val,n->value);
				return;
			}
			else{p_insert(n->right,val);}
 
		}
};
 
node* tree::p_search(node *n, int val){
 
	if(n==nullptr){
		return nullptr;
	}
	else if(n->value==val){
		return n;
	}
	else if(n->value > val){
		return p_search(n->left, val);
	}
	else if(n->value < val){
		return p_search(n->right, val);
	}
}
 
node* tree::p_find_maximum(node* ref){
	if(ref->right==nullptr){
		return ref;
	}
	else{
		return p_find_maximum(ref->right);
	}
}
 
node* tree::p_find_minimum(node* ref){
	if(ref->left==nullptr){
		return ref;
	}
	else{
		return p_find_maximum(ref->left);
	}
}
 
node* tree::p_delete(node *n, int val){
	if(n->value > val){
		n->left = p_delete(n->left,val);
	}
	else if(n->value < val){
		n->right = p_delete(n->right,val);
	}
	else{
	if(n->left==nullptr){
		node* temp_n = n->right;
		free(n);
		return temp_n;
	}
	else if(n->right==nullptr){
		node* temp_n = n->left;
		free(n);
		return temp_n;
	}
 
		node* min_n = p_find_minimum(n->right);
		n->value = min_n->value;
		n->right = p_delete(min_n->right,min_n->value);
 
	}
	return n;
}
 
 
 
int main() {
	tree* abc = new tree(6);
	abc->insertNode(4);
	abc->insertNode(9);
	abc->insertNode(2);
	abc->insertNode(8);
	abc->insertNode(11);
	abc->insertNode(10);
	abc->insertNode(13);
	abc->insertNode(5);
	printf("DFS result : ");
	abc->traverse();
	printf("BFS result : ");
	abc->level_traverse();
	printf("the maximum value of the tree is %d.\n",abc->find_maximum());
	printf("the minimum value of the tree is %d.\n",abc->find_minimum());
	return 0;
}