//BINARY SERACH TREE
#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 *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *, int);
void display(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.Traversals");
 printf("\n\t4.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 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:
 // Display traversals of the BST
 display(root);
 break;
 }
 } while (choice != 4);
 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 perform inorder traversal of the BST
void inorder(node *temp) {
 if (temp != NULL) {
 inorder(temp->lchild);
 printf("%d ", temp->data);
 inorder(temp->rchild);
 }
}
// Function to perform preorder traversal of the BST
void preorder(node *temp) {
 if (temp != NULL) {
 printf("%d ", temp->data);
 preorder(temp->lchild);
 preorder(temp->rchild);
 }
}
// Function to perform postorder traversal of the BST
void postorder(node *temp) {
 if (temp != NULL) {
 postorder(temp->lchild);
 postorder(temp->rchild);
 printf("%d ", temp->data);
 }
}
// 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 display all three traversals of the BST
void display(node *root) {
 if (root == NULL)
 printf("Tree Is Not Created");
 else {
 printf("\n\tThe Inorder display : ");
 inorder(root);
 printf("\n\tThe Preorder display : ");
 preorder(root);
 printf("\n\tThe Postorder display : ");
 postorder(root);
 }
 printf("\n");
}