#include <stdio.
h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a node in the BST
struct Node* insertNode(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
// Function to perform in-order traversal (left, root, right)
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Function to perform pre-order traversal (root, left, right)
void preOrderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// Function to perform post-order traversal (left, right, root)
void postOrderTraversal(struct Node* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// Function to search for a node in the BST
struct Node* searchNode(struct Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchNode(root->left, data);
}
return searchNode(root->right, data);
}
// Function to find the minimum node in the BST
struct Node* findMin(struct Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
// Function to delete a node in the BST
struct Node* deleteNode(struct Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Node with only one child or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
// Node with two children: Get the inorder successor (smallest in the right
subtree)
struct Node* temp = findMin(root->right);
// Copy the inorder successor's content to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Main function
int main() {
struct Node* root = NULL;
int choice, value;
while (1) {
printf("\nBinary Search Tree Operations\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Search\n");
printf("4. In-order Traversal\n");
printf("5. Pre-order Traversal\n");
printf("6. Post-order Traversal\n");
printf("7. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
root = insertNode(root, value);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d", &value);
root = deleteNode(root, value);
break;
case 3:
printf("Enter value to search: ");
scanf("%d", &value);
struct Node* foundNode = searchNode(root, value);
if (foundNode != NULL) {
printf("Value %d found in the tree.\n", foundNode->data);
} else {
printf("Value %d not found in the tree.\n", value);
}
break;
case 4:
printf("In-order Traversal: ");
inOrderTraversal(root);
printf("\n");
break;
case 5:
printf("Pre-order Traversal: ");
preOrderTraversal(root);
printf("\n");
break;
case 6:
printf("Post-order Traversal: ");
postOrderTraversal(root);
printf("\n");
break;
case 7:
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}
