8.
Design and Develop a program in C for the following operations on Binary Search Tree (BST) of
Integers.
i) Create a BST of N Integers
ii) Traverse the BST using Inorder, Preorder and Post Order techniques
iii) Search a KEY element in BST and display the appropriate message
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node *left, *right;
};
// Create a new node
struct Node* createNode(int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert into BST
struct Node* insert(struct Node *root, int value) {
if (root == NULL) {
root = createNode(value);
} else if (value < root->data) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
}
return root;
}
// Inorder Traversal
void inorder(struct Node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Preorder Traversal
void preorder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// Postorder Traversal
void postorder(struct Node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
// Search for a key
int search(struct Node *root, int key) {
if (root == NULL)
return 0;
if (root->data == key)
return 1;
else if (key < root->data)
return search(root->left, key);
else
return search(root->right, key);
}
int main() {
struct Node *root = NULL;
int choice, n, value, key;
while (1) {
printf("\n===== BST MENU =====\n");
printf("1. Create BST with N integers\n");
printf("2. Inorder Traversal\n");
printf("3. Preorder Traversal\n");
printf("4. Postorder Traversal\n");
printf("5. Search for a Key\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &value);
root = insert(root, value);
}
printf("BST Created Successfully.\n");
break;
case 2:
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
break;
case 3:
printf("Preorder Traversal: ");
preorder(root);
printf("\n");
break;
case 4:
printf("Postorder Traversal: ");
postorder(root);
printf("\n");
break;
case 5:
printf("Enter key to search: ");
scanf("%d", &key);
if (search(root, key))
printf("Key %d found in BST.\n", key);
else
printf("Key %d NOT found in BST.\n", key);
break;
case 6:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice! Try again.\n");
}
}
return 0;
}