bst.c

// BINARY  SEARCH TREE


#include<stdio.h>
#include<stdlib.h>
#include <stdbool.h> // bool

struct node
{
  int ele;
  struct node *left;
  struct node *right;
}*root;


struct node *getnode(int data)
{
  struct node *new;
  new=(struct node *)malloc(sizeof(struct node));

  new->ele=data;
  new->left=NULL;
  new->right=NULL;
  return new;
}



void createBT()
{
  int data;
  root=(struct node*)malloc(sizeof(struct node));
  printf("enter the info in 1st node : ");
  scanf("%d",&data);
  root->ele=data;
  root->left=NULL;
  root->right=NULL;
}


struct node *insert(struct node *root, int data)
{
   if (root==NULL)
   {
	     return getnode(data);
   }

   if (data < root->ele)
   {
    root->left=insert(root->left,data);
   } else if (data > root->ele)
   {
    root->right=insert(root->right,data);
   }
   return root;
}

struct node *take_input_and_insert(struct node *root)
{
	int a;
	scanf("%d", &a);
	return insert(root, a);
}


/*
	  2
    1
	
	
	
	  1
        2
*/
void display(struct node* root){
  if(root==NULL)
  {
	  return;
  }

  display(root->left);
  printf("%d ", root->ele);
  display(root->right);

}

void inorder(struct node*root)
{
if(root==NULL)
{
// printf("NULL");
return;
}
printf("[");
inorder(root->left);      //  left
printf("%d,",root->ele);   //  root
inorder(root->right);     //  right
printf("],");
}


void preorder(struct node*root)
{
if(root==NULL)
{
return;
}

printf("%d ",root->ele);   //  root
preorder(root->left);     //  left
preorder(root->right);    //  right

}

void postorder(struct node*root)
{
if(root==NULL)
{
  return;
}

postorder(root->left);    // left
postorder(root->right);   // right
printf("%d ",root->ele);   // root

}

// return values
// 1 : if found
// 0 : if not found
int find_ele(struct node *root, int ele)
{
	if (root == NULL) {
		return 0;
	}
	
	if (root->ele == ele) return 1;
	
	if (ele < root->ele) return find_ele(root->left, ele);
	
	return find_ele(root->right, ele);
}

// find the value which will come just after root in inorder traversal
// assumption: root->right != NULL
int find_next_inorder(struct node* root) {
	// 1. go right : 
	struct node* result = root->right;
	while (result->left != NULL) {
		result = result->left;
	}
	return result->ele;
}


// find_next : node which is next in order
// assumption: val exists in the tree
struct node* delete_node(struct node *root, int val)
{
	// if (root == NULL) : assumption val exists in the tree
	// 1. if val in left tree, delete from left tree
	if (val < root->ele) {
		root->left = delete_node(root->left, val);
		return root;
	}
	// 2. if val in right tree, delete from right tree
	if (root->ele < val) {
		root->right = delete_node(root->right, val);
		return root;
	}
	
	// 3. (Base case 1) : the tree is a leaf
	/*
		root(left = right = NULL)
	
	   5
  null   null
	
	*/
	if (root->left == NULL && root->right == NULL) {
		free(root);
		return NULL;
	}
	
	// 4. (Base case 2) : the tree has only one branch (right)
	// => right branch is now new tree
	/*
	root(left = NULL)
	
	    5
  null     7
	
	
	*/
	if (root->left == NULL) {
		struct node* tmp = root->right;
		free(root);
		return tmp;
	}
	
	// 5. (Base case 3) : the tree has only one branch (right)
	// => left branch is now new tree
	if (root->right == NULL) {
		struct node* new_root = root->left;
		free(root);
		return new_root;
	}
	
	// 6. the root = val, and root has both branches
	// => replace root by next element inorder (replacement)
	// why : 
	// 		1) root->left tree < root->ele < replacement < root->right tree (other than replacement)
	// how: 
	//      1) find next element inorder
	//      2) delete the replacement element from right tree
	//         Note: the replacement element will have at most one branch (right).
	//      3) swap values with replacement
	int replacement = find_next_inorder(root);
	struct node* new_right = delete_node(root->right, replacement);
	
	root->right = new_right;
	root->ele = replacement;
	
	return root;
}



// searching element:-

int main()
{    

  // createBT();
  // postorder(root);

  // printf enter next number
  //
  // for (int i = 0; i < 10; i++) {
  // 	  int a;
  // 	  scanf("%d", &a);
  // 	  root = insert(root, a);
  // }

  // insert(root,90);
  // insert(root,80);

  //insert(root,49);
  //insert(root->left,34);
  //insert(root->left,32);

  // display(root);
  // printf("\n");
  // preorder(root);
  // printf("\n");
  // postorder(root);
  // printf("\n");
  //deleteele(root,32);
  // inorder(root);
  // printf("\n");
   
  char command[100];
  int a;
  while (true) {
	  scanf("%s", command);
	  scanf("%d", &a);
	  if (command[0] == 'f') {
		  printf("%d\n", find_ele(root, a));
	  } else if (command[0] == 'd') {
		  int element_exists = find_ele(root, a);
		  if (element_exists == 0) {
			  printf("the element does not exist\n");
		  } else {
			  root = delete_node(root, a);
		  }
	  } else if (command[0] == 'i') {
		  root = insert(root, a);
	  } else {
          // break;
	  }
	  inorder(root);
      printf("\n");
  }
 }