#include <stdio.h>
#include <stdlib.h>
// 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 = 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 find the minimum value node in the right subtree
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;
}
// Find the node to be deleted
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Node found: let's handle the three cases
// Case 1: No child
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
// Case 2: One child (right)
else if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
// Case 2: One child (left)
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
// Case 3: Two children
struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Function to perform inorder traversal of the BST
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
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("Inorder traversal before deletion: ");
inorder(root);
printf("\n");
// Deleting nodes
root = deleteNode(root, 20); // Deleting a leaf node
printf("Inorder traversal after deleting 20: ");
inorder(root);
printf("\n");
root = deleteNode(root, 30); // Deleting a node with one child
printf("Inorder traversal after deleting 30: ");
inorder(root);
printf("\n");
root = deleteNode(root, 50); // Deleting a node with two children
printf("Inorder traversal after deleting 50: ");
inorder(root);
printf("\n");
return 0;
}
Explanation:
- Node Structure:
- We define a
Nodestructure that holds an integerdata, a pointer to the left child, and a pointer to the right child.
- We define a
- createNode:
- Creates a new node with the given value, setting its left and right pointers to
NULL.
- Creates a new node with the given value, setting its left and right pointers to
- insert:
- Inserts a new node into the BST. If the tree is empty, it creates the root node.
- Otherwise, it compares the data with the current node and inserts it into the left or right subtree accordingly.
- findMin:
- Finds the node with the minimum value in a subtree, which is used to find the inorder successor during deletion.
- deleteNode:
- Recursively locates the node to be deleted.
- Handles the three cases of deletion:
- For a leaf node, it frees the node.
- For a node with one child, it replaces the node with its child.
- For a node with two children, it finds the inorder successor, replaces the node’s value with that of the successor, and deletes the successor.
- inorder:
- Prints the inorder traversal of the tree, which outputs the BST nodes in a sorted order.
- main:
- Demonstrates the insertion of nodes, deletion of specific nodes, and prints the inorder traversal before and after each deletion.
Output:
Inorder traversal before deletion: 20 30 40 50 60 70 80
Inorder traversal after deleting 20: 30 40 50 60 70 80
Inorder traversal after deleting 30: 40 50 60 70 80
Inorder traversal after deleting 50: 40 60 70 80
Explanation of the Output:
- Initially, the BST has nodes
20,30,40,50,60,70, and80. - After deleting
20(a leaf), it’s removed directly. - Deleting
30(which has one child,40), results in40taking its place. - Deleting
50(which has two children) involves replacing50with its inorder successor60, then removing60.
