Example: Design, Develop and Implement a menu driven program using C Programming for the following operations on Binary Search Tree (BST) of Integers.
SOURCE CODE:#include <stdio.h>#include <stdlib.h>struct BST{int data;struct BST *left;struct BST *right;};typedef struct BST NODE;NODE *node;NODE* createtree(NODE *node, int data){if (node == NULL){NODE *temp;temp= (NODE*)malloc(sizeof(NODE));temp->data = data;temp->left = temp->right = NULL;return temp;}if (data < (node->data)){node->left = createtree(node->left, data);}else if (data > node->data){node -> right = createtree(node->right, data);}return node;}NODE* search(NODE *node, int data){if(node == NULL)printf("\nElement not found");else if(data < node->data){node->left=search(node->left, data);}else if(data > node->data){node->right=search(node->right, data);}elseprintf("\nElement found is: %d", node->data);return node;}void inorder(NODE *node){if(node != NULL){inorder(node->left);printf("%d\t", node->data);inorder(node->right);}}void preorder(NODE *node){if(node != NULL){printf("%d\t", node->data);preorder(node->left);preorder(node->right);}}void postorder(NODE *node){if(node != NULL){postorder(node->left);postorder(node->right);printf("%d\t", node->data);}}NODE* findMin(NODE *node){if(node==NULL){return NULL;}if(node->left)return findMin(node->left);elsereturn node;}NODE* del(NODE *node, int data){NODE *temp;if(node == NULL){printf("\nElement not found");}else if(data < node->data){node->left = del(node->left, data);}else if(data > node->data){node->right = del(node->right, data);}else{ /* Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree */if(node->right && node->left){ /* Here we will replace with minimum element in the right sub tree */temp = findMin(node->right);node -> data = temp->data;/* As we replaced it with some other node, we have to delete that node */node -> right = del(node->right,temp->data);}else{/* If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child */temp = node;if(node->left == NULL)node = node->right;else if(node->right == NULL)node = node->left;free(temp); /* temp is longer required */}}return node;}void main(){int data, ch, i, n;NODE *root=NULL;clrscr();while (1){printf("\n1.Insertion in Binary Search Tree");printf("\n2.Search Element in Binary Search Tree");printf("\n3.Delete Element in Binary Search Tree");printf("\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");printf("\nEnter your choice: ");scanf("%d", &ch);switch (ch){case 1: printf("\nEnter N value: " );scanf("%d", &n);printf("\nEnter the values to create BST like(6,9,5,2,8,15,24,14,7,8,5,2)\n");for(i=0; i<n; i++){scanf("%d", &data);root=createtree(root, data);}break;case 2: printf("\nEnter the element to search: ");scanf("%d", &data);root=search(root, data);break;case 3: printf("\nEnter the element to delete: ");scanf("%d", &data);root=del(root, data);break;case 4: printf("\nInorder Traversal: \n");inorder(root);break;case 5: printf("\nPreorder Traversal: \n");preorder(root);break;case 6: printf("\nPostorder Traversal: \n");postorder(root);break;case 7: exit(0);default:printf("\nWrong option");break;}}getch();}OUTPUT:1. Insertion in Binary Search Tree2. Search Element in BinarySearch Tree 3. Delete Element in Binary Search Tree 4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 1Enter N value: 12Enter the values to create BST like(6,9,5,2,8,15,24,14,7,8,5,2)6 9 5 2 8 15 24 14 7 8 5 21. Insertion in Binary Search Tree2. Search Element in Binary Search Tree3. Delete Element in Binary Search Tree4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 4Inorder Traversal:2 5 6 7 8 9 14 15 241. Insertion in Binary Search Tree2. Search Element in Binary Search Tree3. Delete Element in Binary Search Tree4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 5Preorder Traversal:6 5 2 9 8 7 15 14 241. Insertion in Binary Search Tree2. Search Element in Binary Search Tree 3. Delete Element in Binary Search Tree 4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 6Postorder Traversal:2 5 7 8 14 24 15 9 61. Insertion in Binary Search Tree2. Search Element in Binary Search Tree3. Delete Element in Binary Search Tree4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 3Enter the element tosearch: 151. Insertion in Binary Search Tree2. Search Element in Binary Search Tree3. Delete Element in Binary Search Tree4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 4Inorder Traversal:2 5 6 7 8 9 14 241. Insertion in Binary Search Tree2. Search Element in Binary Search Tree3. Delete Element in Binary Search Tree4. Inorder5. Preorder6. Postorder7. ExitEnter your choice: 5Preorder Traversal:6 5 2 9 8 7 24 14