#include <stdio.h>
#include <stdlib.h>
// Structure for a node in the Binary Search Tree
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));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a node into 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);
}
// Ignore duplicates for simplicity
return root;
}
// Function to search for a key in the BST
struct Node* searchNode(struct Node* root, int key) {
if (root == NULL || root->data == key) {
return root;
}
if (key < root->data) {
return searchNode(root->left, key);
}
return searchNode(root->right, key);
}
// Function to find the node with the minimum value in a BST
struct Node* findMin(struct Node* root) {
while (root && root->left != NULL) {
root = root->left;
}
return root;
}
// Function to delete a node from the BST
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) {
return root;
}
if (key < root->data) {
root->left = deleteNode(root->left, key);
} else if (key > root->data) {
root->right = deleteNode(root->right, key);
} 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 right subtree)
struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Function for Inorder Traversal (Left -> Root -> Right)
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Main function to test BST operations
int main() {
struct Node* root = NULL;
// Insert nodes into the BST
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 70);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 60);
insertNode(root, 80);
// Print the BST using inorder traversal
printf("Inorder Traversal (Sorted Order): ");
inorderTraversal(root);
printf("\n");
// Test search
int key = 40;
struct Node* result = searchNode(root, key);
if (result) {
printf("Found key %d in the BST\n", key);
} else {
printf("Key %d not found in the BST\n", key);
}
// Test deletion
printf("Deleting key 30...\n");
root = deleteNode(root, 30);
printf("Inorder Traversal after deletion: ");
inorderTraversal(root);
printf("\n");
// Test deletion of a non-existent key
printf("Deleting key 100...\n");
root = deleteNode(root, 100);
printf("Inorder Traversal after deletion: ");
inorderTraversal(root);
printf("\n");
return 0;
}
Output:
Comments
Post a Comment