How to delete a node in Binary Search Tree?
As we discussed the basic operations in Binary Search Tree, here we implement the delete operation in Binary Search Tree.
Deletion can be implemented as three types.
·
Node has one child – you can replace the node
with its child node.
·
Node has two children – it changes the node to
the smallest value in the right
Subtree and deleted the successor.
· Node has no child – it deletes the node.
#include <stdio.h>
#include <stdlib.h>
// Create BST node
int b_data;
struct BST_Node
*b_left, *b_right;
};
//code to create a new node
struct BST_Node* newNode(int value) {
struct BST_Node*
temp = (struct BST_Node*)malloc(sizeof(struct BST_Node));
temp->b_data =
value;
temp->b_left =
temp->b_right = NULL;
return temp;
}
// implement Inorder traversal
void inorder(struct BST_Node* root) {
if (root != NULL)
{
inorder(root->b_left);
printf("%d ", root->b_data);
inorder(root->b_right);
}
}
// function to find minimum value node
struct BST_Node* minValueNode(struct BST_Node* node) {
struct BST_Node*
current = node;
while (current
&& current->b_left != NULL)
current =
current->b_left;
return current;
}
// Delete a node
struct BST_Node* deleteNode(struct BST_Node* root, int key)
{
if (root == NULL)
return root;
// Traverse the
tree
if (key <
root->b_data)
root->b_left = deleteNode(root->b_left, key);
else if (key >
root->b_data)
root->b_right = deleteNode(root->b_right, key);
else {
// Node is
found
// Case 1: No
child
if
(root->b_left == NULL && root->b_right == NULL) {
free(root);
return
NULL;
}
// Case 2: One
child
if
(root->b_left == NULL) {
struct
BST_Node* temp = root->b_right;
free(root);
return
temp;
}
else if
(root->b_right == NULL) {
struct
BST_Node* temp = root->b_left;
free(root);
return
temp;
}
// Case 3: Two
children
struct
BST_Node* temp = minValueNode(root->b_right);
root->b_data = temp->b_data;
root->b_right = deleteNode(root->b_right, temp->b_data);
}
return root;
}
// Insert a node into BST
struct BST_Node* insert(struct BST_Node* node, int key) {
if (node == NULL)
return newNode(key);
if (key <
node->b_data)
node->b_left = insert(node->b_left, key);
else if (key >
node->b_data)
node->b_right = insert(node->b_right, key);
return node;
}
// main function
int main() {
int a=0;
struct BST_Node*
root = NULL;
root =
insert(root, 55);
root =
insert(root, 33);
root =
insert(root, 18);
root =
insert(root, 45);
root =
insert(root, 74);
root =
insert(root, 69);
root =
insert(root, 100);
printf("Inorder traversal of BST: ");
inorder(root);
printf("\nEnter the number to delete");
scanf("%d",&a);
root =
deleteNode(root,a);
inorder(root);
printf("\nEnter
another node to Delete \n");
scanf("%d",&a);
root =
deleteNode(root,a);
inorder(root);
printf("\nEnter
another node to Delete \n");
scanf("%d",&a);
root =
deleteNode(root,a);
inorder(root);
return 0;
}
Output:
Inorder traversal of BST: 18 33 45 55 69 74 100
Enter the number to delete33
18 45 55 69 74 100
Enter another node to Delete
69
18 45 55 74 100
Enter another node to Delete
100
18 45 55 74
That’s all. The delete operation in Binary Search Tree is
implemented successfully. Hope, you understood the concept. Keep Coding!!!
Comments
Post a Comment