//Deletion of a node from BST
//AIM: Develop a c program to perform the deletion of a node from BST

#include <stdio.h>
#include <stdlib.h>
// Define the structure for a binary search tree (BST) node
typedef struct BST {
 int data;
 struct BST *lchild, *rchild;
} node;
// Function prototypes
node *get_node();
void insert(node *, node *);
node *search(node *, int);
node *delete_node(node *, int);
void display(node *);
void inorder(node *);
int main() {
 int choice;
 int key;
 node *new_node, *root, *tmp;
 root = NULL;
 // Display initial program information
 printf("\n\n\tProgram For Binary Search Tree");
 printf("\n\n\t------------------------------");
 // Menu-driven program
 char ans; // Declare ans outside the loop
 do {
 printf("\n");
 printf("\n\tMenu");
 printf("\n\t----");
 printf("\n\t1.Create");
 printf("\n\t2.Search");
 printf("\n\t3.Delete");
 printf("\n\t4.Display");
 printf("\n\t5.Exit");
 printf("\n\tEnter your choice: ");
 scanf("%d", &choice);
 switch (choice) {
 case 1:
 // Create a new node and insert it into the BST
 do {
 new_node = get_node();
 printf("\tEnter The Element: ");
 scanf("%d", &new_node->data);
 if (root == NULL)
 root = new_node;
 else
 insert(root, new_node);
 // Ask the user if they want to enter more elements
 printf("\tWant To enter More Elements?(y/n): ");
 scanf(" %c", &ans);
 // If yes, display a separator line
 if (ans == 'y') {
 printf("\n----------------\n");
 }
 } while (ans == 'y');
 break;
 case 2:
 // Search for an element in the BST
 printf("\tEnter Element to be searched: ");
 scanf("%d", &key);
 tmp = search(root, key);
 if (tmp != NULL) {
 printf("\n\tElement %d is Present", tmp->data);
 } else {
 printf("\n\tElement not present");
 }
 break;
 case 3:
 // Delete a node from the BST
 printf("\tEnter Element to be deleted: ");
 scanf("%d", &key);
 root = delete_node(root, key);
 break;
 case 4:
 // Display the BST
 display(root);
 break;
 }
 } while (choice != 5);
 return 0;
}
// Function to create a new node for the BST
node *get_node() {
 node *temp = (node *)malloc(sizeof(node));
 temp->lchild = NULL;
 temp->rchild = NULL;
 return temp;
}
// Function to insert a new node into the BST
void insert(node *root, node *new_node) {
 if (new_node->data < root->data) {
 if (root->lchild == NULL)
 root->lchild = new_node;
 else
 insert(root->lchild, new_node);
 } else if (new_node->data > root->data) {
 if (root->rchild == NULL)
 root->rchild = new_node;
 else
 insert(root->rchild, new_node);
 }
}
// Function to search for an element in the BST
node *search(node *root, int key) {
 if (root == NULL || root->data == key)
 return root;
 if (key < root->data)
 return search(root->lchild, key);
 else
 return search(root->rchild, key);
}
// Function to delete a node from the BST
node *delete_node(node *root, int key) {
 if (root == NULL)
 return root;
 // Recursive calls for searching the key to be deleted
 if (key < root->data)
 root->lchild = delete_node(root->lchild, key);
 else if (key > root->data)
 root->rchild = delete_node(root->rchild, key);
 // Node with only one child or no child
 else {
 if (root->lchild == NULL) {
 node *temp = root->rchild;
 free(root);
 return temp;
 } else if (root->rchild == NULL) {
 node *temp = root->lchild;
 free(root);
 return temp;
 }
 // Node with two children
 node *temp = root->rchild;
 while (temp->lchild != NULL)
 temp = temp->lchild;
 // Copy the inorder successor's content to this node
 root->data = temp->data;
 // Delete the inorder successor
 root->rchild = delete_node(root->rchild, temp->data);
 }
 return root;
}
// Function to display the BST using inorder traversal
void display(node *root) {
 if (root == NULL)
 printf("Tree Is Not Created");
 else {
 printf("\n\tThe Inorder display : ");
 inorder(root);
 }
 printf("\n");
}
// Function to perform inorder traversal of the BST
void inorder(node *temp) {
 if (temp != NULL) {
 inorder(temp->lchild);
 printf("%d ", temp->data);
 inorder(temp->rchild);
 }
}