#include <stdio.h>
#include <iostream>
#include <stdlib.h>

typedef struct node
{
	int value;
	node* right;
	node* left;
} node;
#undef root;

node* add_node(node* root, int value);
node* delete_node(node* root, int value);
void print_tree(node* root);
void clear_tree(node* root);
node* get_max(node* root);
node* get_min(node* root);
node* search_and_destraction(node* root, node* del, int flag);

int main()
{
	node* root = NULL;
	root=add_node(root,34);
	root=add_node(root,53);
	root = add_node(root,456);
	root = add_node(root,3);
	root = add_node(root,31);
	print_tree(root);
	delete_node(root, 53);
	delete_node(root, 10);
	print_tree(root);
	clear_tree(root);
}

node* add_node(node* root, int value)
{
	if (!root)
	{
		root = (node*)malloc(sizeof(node));
		root->value = value;
		root->right = NULL;
		root->left = NULL;
		return root;
	}
	else
	{
		if (root->value == value)
		{
			return root;
		}
		if (root->value > value)
		{
			root->left =add_node(root->left, value);
			return root;
		}
		else
		{
			root->right =add_node(root->right, value);
			return root;
		}
	}
}



node* delete_node(node* root, int value)
{
	if (root == NULL)
	{
		return root;
	}


	if (root->value > value)
	{
		root->left = delete_node(root->left, value);
	}
	if (root->value < value)
	{
		root->right = delete_node(root->right, value);
	}

	if (root->value == value)
	{
		node* temp;
		if ((root->left)&&(root->right))
		{
			root = get_max(root->left);
			int max_num = get_max(root->left)->value;
			int min_num = get_min(root->right)->value;
			if ((root->value - max_num) <= (min_num - root->value))
			{
				delete_node(root, max_num);
				root->value=max_num;
			}
			else
			{
				delete_node(root, min_num);
				root->value = min_num;
			}

		}
		if ((!root->left) && (!root->right))
		{
			free(root);
			return NULL;
		}
		if ((root->left) && (!root->right))
		{
			temp = root->left;
			free(root);
			return temp;
		}
		if ((!root->left) && (root->right))
		{
			temp = root->right;
			free(root);
			return temp;
		}

	}
	return root;
}



node* search_and_destraction(node* root, node* del, int flag)
{
	if (flag)
	{
		node* temp = root;
		root = del->left;
		del->left = del->left->right;
		free(temp);
	}
	else
	{
		node* temp = root;
		root = del->right;
		del->right = del->right->left;
		free(temp);
	}
	return root;
}



void print_tree(node* root)
{
	if (!root)
	{
		return;
	}
	if (root->left)
	{
		print_tree(root->left);
	}
	printf("\n%3d", root->value);
	if (root->right)
	{
		print_tree(root->right);
	}
}



void clear_tree(node* root)
{
	if (!root)
	{
		return;
	}
	if (root->left)
	{
		clear_tree(root->left);
	}
	if (root->right)
	{
		clear_tree(root->right);
	}
	free(root);
}



node* get_max(node* root)
{
	node* temp = root;
	while ((temp->right->right) && (temp->right))
	{
		temp = temp->right;
	}
	return root;

}



node* get_min(node* root)
{
	node* temp = root;
	while (temp->left)
	{
		temp = temp->left;
	}
	return temp;
}