#include <stdio.h>
#include <stdlib.h>
// Define the structure for a node in the BST
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 new node in the BST
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
// Function to perform in-order traversal (left, root, right)
void inOrder(struct Node* root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
// Function to search for a value in the BST
struct Node* search(struct Node* root, int key) {
if (root == NULL || root->data == key) {
return root;
}
if (key < root->data) {
return search(root->left, key);
}
return search(root->right, key);
}
// Function to find the minimum value node in a BST
struct Node* findMin(struct Node* node) {
struct Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
// Function to delete a node from the BST
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) {
return root;
}
// Recur down the tree
if (key < root->data) {
root->left = deleteNode(root->left, key);
} else if (key > root->data) {
root->right = deleteNode(root->right, key);
} else {
// Node to be deleted found
// 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
struct Node* temp = findMin(root->right);
// Copy the inorder successor's data to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Main function to test the BST
int main() {
struct Node* root = NULL;
// Insert nodes into the BST
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("In-order traversal of the BST: ");
inOrder(root);
printf("\n");
// Search for a value
int key = 40;
struct Node* foundNode = search(root, key);
if (foundNode != NULL) {
printf("Node %d found in the BST.\n", key);
} else {
printf("Node %d not found in the BST.\n", key);
}
// Delete a node
root = deleteNode(root, 20);
printf("In-order traversal after deleting 20: ");
inOrder(root);
printf("\n");
return 0;
}
Explanation:
Structure Definition:
struct Node: Represents a node of the BST. It contains:
data: The value of the node.
left: Pointer to the left child.
right: Pointer to the right child.
Creating a Node:
createNode(int data): Allocates memory for a new node, sets its data, and initializes left and right pointers to NULL.
Inserting a Node:
insert(struct Node* root, int data): Recursively inserts a new node:
If root is NULL, the new node is inserted at this position.
If data is less than the current node’s data, it is inserted in the left subtree.
If data is greater, it is inserted in the right subtree.
In-order Traversal:
inOrder(struct Node* root): Prints nodes in ascending order by recursively visiting the left subtree, root, and then the right subtree.
Searching:
search(struct Node* root, int key): Recursively searches for key:
If key matches the current node’s data, it is found.
If key is less, search the left subtree.
If key is greater, search the right subtree.
Deleting a Node:
deleteNode(struct Node* root, int key): Removes a node while maintaining BST properties:
Searches for the key to delete.
Handles three cases:
Node with only one child or no child.
Node with two children: Replaces the node with its in-order successor (minimum node from the right subtree).
Main Function:
Tests the BST by inserting nodes, performing an in-order traversal, searching for a value, deleting a node, and displaying the modified tree.
In-order traversal of the BST: 20 30 40 50 60 70 80
Node 40 found in the BST.
In-order traversal after deleting 20: 30 40 50 60 70 80
Explanation of Output:
In-order Traversal: Displays the BST elements in sorted order.
Node 40 found: Indicates that the search operation successfully located the node with value 40.
After Deletion: Shows the in-order traversal after deleting the node with value 20.
