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


 struct Node{

	int data;
    struct Node* left;
    struct  Node* right;

};

 struct Node* GetnewNode(int data) //15,10,20
 {
	 struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
	 newNode->data = data;
	 newNode->left = newNode->right = NULL;
	 return newNode;
 }

 struct Node* insert(struct Node* root, int data) //15,10,20
{
	 if (root == NULL)
	 {
		 root = GetnewNode(data);//15,10,20
	 }

	 else if (data <= root->data) //10<15,20<15
	 {
		 root->left = insert(root->left, data);   //10 < =20    main->insert(200,10) -> insert(0,10) ->
		     //  return address of 0,10  then return address of root to main
	 }
	 else
	 {
		 root->right = insert(root->right, data); //main->(200,20)->insert(0,20)- return address of 0,20 , return address of root
	 }

		 return root ;
}

 int search(struct Node* root, int data) //10
 {
	 if (root == NULL)
		 return 0;
	 else if (root->data == data)
		 return 1;
	 else if (data <= root->data) //10<15
		 return search(root->left, data);
	 else
		 return search(root->right, data);
 }

 struct Node* findMin(struct Node* data)
 {
	 struct Node* current = data;

	 /* loop down to find the leftmost leaf */
	 while (current->left != NULL)
		 current = current->left;

	 return current;
 }


 struct Node* delete(struct Node* root, int data)
 {
     if(root == NULL) return root;
     else if(data < root->data) root->left = delete(root->left,data);
          else if(data > root->data) root->right = delete(root->right,data);
          else
          {
              //case 1 : no child
              if(root->left==NULL && root->right == NULL)
              {

                  free(root);
                  root=NULL;
                  return root;
                  //case 2 : one child
              }
              else if(root->left == NULL)
              {
                  struct Node* temp = root;
                  root = root->right ;
                  free(temp);
                  return root;


              }

              else if(root->right == NULL)
              {
                  struct Node* temp = root;
                  root = root->left ;
                  free(temp);
                  return root;

              }
              else
              {
                  struct Node* temp = findMin(root->right);
                   // Copy the inorder successor's content to this node
                  root->data = temp ->data ;

                  // Delete the inorder successor
                  root->right = delete(root->right,temp->data);

              }

          }

 }


int main()
{
	struct  Node*  root = NULL;
	int n,s,d;
	int choich;


 	do {



        printf("Please Select anyone......\n\n");
		printf(" 1.insert \n 2.search \n 3.delete \n");
		scanf("%d", &choich);
		switch (choich)
		{
		case 1:
			printf("Enter the number : ");
			scanf("%d", &n);
			root = insert(root, n); //15,10,20
			break;

		case 2:
		    printf("enter the number u want to search..\n");
			scanf("%d", &s); //10

			if(search(root,s)==1)
            {
                printf("Found..\n");
            }
            else
            {
                printf("Not found\n");
            }
			break;

		case 3:
			printf("enter the number u want to delete..\n");
			scanf("%d", &d);
			delete(root,d);
			break;

		default:
			printf("Invalid option selected! Please select right option..\n\n");
		}
	}
	while (choich != 0);

}