#include <iostream>


struct tree
{
	int data;
	tree* right;
	tree* left;
	tree* middle;

};

tree* DeleteNode(tree* node, int val) {
	if (node == NULL)
		return node;

	if (val == node->data) {

		tree* tmp;
		if (node->right == NULL)
			tmp = node->left;
		else {

			tree* ptr = node->right;
			if (ptr->left == NULL) {
				ptr->left = node->left;
				tmp = ptr;
			}
			else {

				tree* pmin = ptr->left;
				while (pmin->left != NULL) {
					ptr = pmin;
					pmin = ptr->left;
				}
				ptr->left = pmin->right;
				pmin->left = node->left;
				pmin->right = node->right;
				tmp = pmin;
			}
		}

		delete node;
		return tmp;
	}
	else if (val < node->data)
		node->left = DeleteNode(node->left, val);
	else
		node->right = DeleteNode(node->right, val);
	return node;
}


void add(int data, tree*& node)
{
	if (!node)
	{
		node = new tree();
		node->data = data;
		node->right = NULL;
		node->left = NULL;
		node->middle = NULL;
		return;
	}

	if (data < node->data)
	{

		add(data, node->left);
	}
	else if (data > node->data)
	{

		add(data, node->right);
	}
	else
	{
		add(data, node->middle);
	}

}

void print(tree*& node)
{
	if (!node)
	{
		return;
	}
	print(node->left);
	std::cout << node->data << ",";
	print(node->middle);
	print(node->right);

}

void print2(tree* node)
{
	if (!node)
	{
		return;
	}
	std::cout << node->data << ",";
	print(node->left);
	print(node->middle);
	print(node->right);
}

void search(tree* node, int key)
{
	if (node == NULL) return;
	if (key == node->data)
	{
		std::cout << "node " << node->data << std::endl;
		if (node->middle)
		{
			std::cout << "Middle half of tree" << std::endl;
			return;
		}
		if (node->left)
		{
			std::cout << "left child " << node->left->data << std::endl;
		}
		else
			std::cout << "Non left child " << std::endl;
		if (node->right)
		{
			std::cout << "right child " << node->right->data << std::endl;
		}
		else
			std::cout << "Non right child " << std::endl;

	}
	search(node->left, key);
	search(node->right, key);

}

void deleting(tree* node)
{
	if (node)
	{
		deleting(node->left);
		deleting(node->right);
		deleting(node->middle);
		delete node;
		node = nullptr;
	}
}


void menu()
{
	std::cout << std::endl;
	std::cout << "1-Add integer" << std::endl;
	std::cout << "2-Show tree by 1 variant" << std::endl;
	std::cout << "3-Show tree by 2 variant" << std::endl;
	std::cout << "4-Delete integer" << std::endl;
	std::cout << "5-Delete all tree" << std::endl;
	std::cout << "6-search integer" << std::endl;
	std::cout << "7-Exit the program" << std::endl;
}



int main()
{
	tree* root = NULL;
	for (;;)
	{
		int data;
		int m;
		menu();
		std::cin >> m;
		switch (m)
		{
		case 1:


			std::cout << "Enter integer" << std::endl;
			std::cin >> data;
			add(data, root);
			break;

		case 2:

			print(root);
			break;
		case 3:
			print2(root);
			break;

		case 4:

			std::cout << "What integer do you want to delete" << std::endl;
			int z;
			std::cin >> z;
			DeleteNode(root, z);
			break;
		case 5:
			deleting(root);
			std::cout << "tree had been deleted" << std::endl;
			break;
		case 6:
			std::cout << "Enter integer that you want to search" << std::endl;
			int l;
			std::cin >> l;
			search(root, l);
			break;

		case 7:

			return 0;
		}
	}


}