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


typedef struct node {
	int value;
	node* right;
	node* left;
} node;
void cleartree(node* root);
void print_tree(node* rootr);
node* add_node(node* rootr, int value);
node* getmin(node* root);
node* getmax(node* root);
node* deletenode(node* root, int value);


int main()
{
	node* rootr = NULL;

	rootr = add_node(rootr, 45);
	rootr = add_node(rootr, 51);
	rootr = add_node(rootr, 35);
	rootr = add_node(rootr, 23);
	rootr = add_node(rootr, 65);
	rootr = add_node(rootr, 105);
	rootr = add_node(rootr, 57);
	rootr = add_node(rootr, 34);
	rootr = add_node(rootr, 65);
	rootr = add_node(rootr, 45);
	deletenode(rootr, 23);
	print_tree(rootr);
	return 0;
}

node* add_node(node* rootr, int value) {
	node* new_node = (node*)malloc(sizeof(node));
	new_node->value = value;
	new_node->left = NULL;
	new_node->right = NULL;
	if (rootr == NULL) {
		return new_node;
	}
	node* curr = rootr;
	while (curr) {
		if (curr->value == value) {
			free(new_node);
			return rootr;
		}
		if (curr->value < value) {
			if (curr->right != NULL) {
				curr = curr->right;
				continue;
			}
			else {
				curr->right = new_node;
				return rootr;
			}
		}
		if (curr->value > value) {
			if (curr->left != NULL) {
				curr = curr->left;
				continue;
			}
			else {
				curr->left = new_node;
				return rootr;
			}
		}
	}
	return rootr;
}

node* deletenode(node* root, int value) {
	if (!root) {
		return NULL;
	}
	if (root->value > value) {
		root->left = deletenode(root->left, value);
	}
	if (root->value < value) {
		root->right = deletenode(root->right, value);
	}
	if (root->value == value) {
		if (!root->left && !root->right) {
			free(root);
			return NULL;
		}
		node* temp = 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;
		}
		if (root->left && root->right) {
			int maxleft = getmax(root->left)->value;
			int minright = getmin(root->right)->value;
			if (root->value - maxleft < minright - root->value) {
				deletenode(root, maxleft);
				root->value = maxleft;
			}
			else {
				deletenode(root, minright);
				root->value = minright;
			}
		}


	}
	return root;
}

void print_tree(node* rootr) {
	if (rootr->left) {
		print_tree(rootr->left);
	}
	printf("%4d", rootr->value);

	if (rootr->right) {
		print_tree(rootr->right);
	}
	return;
}

void cleartree(node* root) {
	if (root) {
		if (root->left) {
			cleartree(root->left);
		}
		if (root->right) {
			cleartree(root->right);
		}
		free(root);
	}
}





node* getmin(node* root) {
	node* temp = root;
	while (temp->left) {
		temp = temp->left;
	}
	return temp;
}
node* getmax(node* root) {
	node* temp = root;
	while (temp->right) {
		temp = temp->right;
	}
	return temp;
}