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

typedef struct Node
{
	int key;
	struct Node* left;
	struct Node* right;
	struct Node* parent;
} Node;

typedef struct BST
{
	Node* root;
} BST;

Node* new_node(int val);
void init_tree(BST* bst);
void inorder_tree_walk(Node *x);
void preorder_tree_walk(Node *x);
void postorder_tree_walk(Node *x);
Node* tree_search(Node *x, int k);
Node* tree_minimum(Node *x);
Node* tree_maximum(Node *x);
Node* tree_successor(Node* x);
void tree_insert(BST* T, Node* z);
void transplant(BST* T, Node* u, Node* v);
void tree_delete(BST* T, Node* z);




int main(void)
{
    BST tree;
	init_tree(&tree);
	BST* ptree = &tree;
	
    tree_insert(ptree, new_node(30));
    tree_insert(ptree, new_node(40));
    tree_insert(ptree, new_node(50));
    tree_insert(ptree, new_node(10));
    
    Node* found_10 = tree_search(ptree->root, 10);
    tree_delete(ptree, found_10);
	
    if (tree_search(ptree->root, 40) != NULL) tree_delete(ptree, tree_search(ptree->root, 40));
	
    printf("Inorder traversal of the given tree \n");
    inorder_tree_walk(ptree->root);
 
}

Node* new_node(int val)
{
    Node* temp_node =  (Node*)malloc(sizeof(Node));
    temp_node->key = val;
    temp_node->left = temp_node->right = temp_node->parent = NULL;
 
    return temp_node;
}

void init_tree(BST* bst)
{
	bst->root = NULL;
}

void inorder_tree_walk(Node *x)
{
	if (x != NULL)
	{
		inorder_tree_walk(x->left);
		printf("%d ", x->key);
		inorder_tree_walk(x->right);
    }
}

void preorder_tree_walk(Node *x)
{
	if (x != NULL)
	{
		printf("%d ", x->key);
		preorder_tree_walk(x->left);
		preorder_tree_walk(x->right);
    }
}

void postorder_tree_walk(Node *x)
{
	if (x != NULL)
	{
		postorder_tree_walk(x->left);
		postorder_tree_walk(x->right);
		printf("%d ", x->key);
    }
}

Node* tree_search(Node *x, int k)
{
	if ((x == NULL) || (k == x->key))
		return x;
	if (k < x->key)
		return tree_search(x->left, k);
	else return tree_search(x->right, k);
}

Node* tree_minimum(Node *x)
{
	while (x->left != NULL)
		x = x->left;
	return x;
}

Node* tree_maximum(Node *x)
{
	while (x->right != NULL)
		x = x->right;
	return x;
}

Node* tree_successor(Node* x)
{
	if (x->right != NULL)
		return tree_minimum(x->right);
	
	Node* y = x->parent;
	while ((y != NULL) && (x == y->right))
	{
		x = y;
		y = y->parent;
	}
	return y;
}

void tree_insert(BST* T, Node* z)
{
	Node* y = NULL;
	Node* x = T->root;
	while (x != NULL)
	{
		y = x;
		if (z->key < x->key)
			x = x->left;
		else x = x->right;
	}
	z->parent = y;
	
	if (y == NULL)
		T->root = z;
	else if (z->key < y->key)
		y->left = z;
	else y->right = z;
}

void transplant(BST* T, Node* u, Node* v)
{
	if (u->parent == NULL)
		T->root = v;
	else if (u == u->parent->left)
		u->parent->left = v;
	else u->parent->right = v;
	
	if (v != NULL)
		v->parent = u->parent;
}

void tree_delete(BST* T, Node* z)
{
	if (z->left == NULL)
		transplant(T, z, z->right);
	else if (z->right == NULL)
		transplant(T, z, z->left);
	else 
	{
		Node* y = tree_minimum(z->right);
		if (y->parent != z)
		{
			transplant(T, y, y->right);
			y->right = z->right;
			y->right->parent = y;
		}
		transplant(T, z, y);
		y->left = z->left;
		y->left->parent = y;
	}
}