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

struct node
{
	struct node *left;
	int data;
	struct node *right;
};

void insert(struct node **root, int data);
void search(struct node** root, int data);
struct node * searchloc(struct node **root, int data);
void delete(struct node **root, int data);
struct node * searchparent(struct node **root, struct node *temp);
struct node * inorder(struct node *root, struct node *temp);

int main(void)
{

	//printf("\n %d", SIZE);
	struct node *root = NULL;
	int data;
	char ch;

	do
	{
		printf("\n Enter the data\n");
		scanf("%d", &data);
		insert(&root, data);
		printf("\n Do you want to add more elements\n");
		scanf("\n%c", &ch);
	}while(ch == 'y' || ch == 'Y');

	printf("\n Do you want to search data");
	scanf("\n %c", &ch);
	while(ch == 'y' || ch == 'Y')
	{
	printf("\n Enter the data to search in the BST");
	scanf("\n %d", &data);
	search(&root, data);
	printf("\n Do you want to search data");
	scanf("\n %c", &ch);
	}

	delete(&root, 8);
	return 0;
}

void delete(struct node **root, int data)
{
	struct node *temp = NULL;
	struct node ** r;
	struct node *parent;
	struct node *insuc;

	r = root;
	// find where is the data that is get the address
	temp = searchloc(r, data);

	if(temp != NULL)
			printf("\n Location at which element was found is %p", temp);
	else
	{
		printf("\n The data that you tried to delete doesnt exist in the list");
		return;
	}

	r = root;
	// get the parents address as well
	parent = searchparent(*r, temp);

	if(parent != NULL)
		printf("\n Location at which parent was found is %p", parent);

	// the location where the element has been found has no children
	// simply delete the element and move ahead
	if(temp->left == NULL && temp->right == NULL)
	{
		// set the pointer in the parent to null
		if(parent->left == temp)
			parent->left = NULL;
		else if (parent->right == temp)
			parent->right = NULL;

		free(temp);
	}

	// the location where the element has been found has one children
	// set the pointer in the parent to point to the child
	if(temp->left == NULL && temp->right != NULL)
	{
		if(parent->left == temp)
			parent->left = temp->right;
		else if(parent->right == temp)
			parent->right = temp->right;

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

		free(temp);
		return;
	}

	// the location where the element has been found has two children
	// 1. Find the inorder successor
	// 2. Copy its data to the node being deleted
	// 3. The inorder successor will always have one or no child
	// which reduces the problem to deletion of a node with one or zero child

	if(temp->left != NULL && temp->right != NULL)
	{
		// find the location of the inorder successor
		insuc =	inorder(root, temp);
		printf("\n Location of inorder successor is %p and its value is %d", insuc, insuc->data);
	}
}

struct node * inorder(struct node **root, struct node *temp)
{
	int i = 0;
	if((*root) != NULL)
	{
		inorder((*root)->left, temp);
		if(temp->data == (*root)->data)
		{
			printf("\n %d", (*root)->data);
			++ i;
		}
		// next time i come here with value of i being 1 i would have got the inorder successor 
		else
		{
			if(i == 1)
			{
				return (*root);
			}
			else
				printf("\n Still searching");
		}
		inorder((*root)->right, temp);
	}
}

struct node * searchparent(struct node *root, struct node *temp)
{
	if(root->left != NULL && root->left == temp)
	{
		return root;
	}
	else if(root->left != NULL)
	{
		searchparent(root->left, temp);
		if(root->right != NULL)
			searchparent(root->right, temp);
	}

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

struct node * searchloc(struct node **root, int data)
{

	if((*root)->data == data)
	{
		printf("\n Data Found in the tree");
		return (*root);
	}
	// search in the left of the root
	else if((*root)->data < data)
	{
		if((*root)->right != NULL)
		{
			searchloc(&(*root)->right, data);
		}
		else
		{
			printf("\n Data not in the tree");
			return NULL;
		}
	}
	// search in the right of the root
	else if((*root)->data > data)
	{
		if((*root)->left != NULL)
		{
		searchloc(&(*root)->left, data);
		}
		else
		{
			printf("\n Data not in the tree");
			return NULL;
		}
	}
	else
	{
		printf("\n Data does not exist in the tree");
		return NULL;
	} 

}


void search(struct node** root, int data)
{
	if((*root)->data == data)
	{
		printf("\n Data Found in the tree");
		return;
	}
	// search in the left of the root
	else if((*root)->data < data)
	{
		if((*root)->right != NULL)
		{
			search(&(*root)->right, data);
		}
		else
		{
			printf("\n Data not in the tree");
			return;
		}
	}
	// search in the right of the root
	else if((*root)->data > data)
	{
		if((*root)->left != NULL)
		{
		search(&(*root)->left, data);
		}
		else
		{
			printf("\n Data not in the tree");
			return;
		}
	}
	else
	{
		printf("\n Data does not exist in the tree");
		return;
	} 
}

void insert(struct node **root, int data)
{
	
	struct node *temp;

	// check if its the first element that i am going to add
	if(*root == NULL)
	{
		*root = (struct node *) malloc(sizeof(struct node));
		(*root)->left = NULL;
		(*root)->right = NULL;
		(*root)->data = data;
		return;
	}
	// this is not the first element
	// find its correct place in the tree
	// data is larger than root so put in the right
	else
	{
		if((*root)->data < data)
		{
			insert(&((*root)->right), data);
		}
	
		else if((*root)->data > data)
		{
			insert(&((*root)->left), data);
		}
	}
}