Deletion of a node in a BST can be more complicated task than searching or inserting a node.
Suppose we want to delete a node P
1> If P is a leaf node i.e. it has no children, then we will just replace P by null.
8 8
/ \ delete(9) / \
3 10 ----------> 3 10
/ \ / / \
1 5 9 1 5
2> If P has only one child, then we will place the child to P's place.
8 8
/ \ delete(10) / \
3 10 ----------> 3 9
/ \ / / \
1 5 9 1 5
3>If P has two children, then we will identify P's successor. Call it Q. The successor Q either is a leaf or has only the right child. We will replace P by Q and delete Q.(if it has right child then follow method 2)
8 9
/ \ delete(8) / \
3 10 ----------> 3 10
/ \ / / \
1 5 9 1 5
C Program
#include <stdio.h>
#include <stdlib.h>
typedef struct BST
{
struct BST *lc, *rc;
int data;
}BST;
BST *insertNode(BST *T,int item)
{
BST *curr = T,*prev = NULL,*temp = NULL;
int found = 0;
//Search for the proper position of the node to insert...
while(curr != NULL && !found)
{
//Keeping track of the previous node...
prev = curr;
// If item already exists...
if(curr->data == item)
{
found = 1;
printf("\nItem %d Already Exists In The BST.\n",item);
}
else if(curr->data > item) {
curr = curr->lc;
}
else {
curr = curr->rc;
}
}
//Creating a new node...
temp = (BST*)malloc(sizeof(BST));
temp->data = item;
temp->lc = NULL;
temp->rc = NULL;
//Only for first node or time...
if(T == NULL)
T = temp;
else if(item > prev->data)
prev->rc = temp;
else
prev->lc = temp;
return T;
}
void inorder(BST *t)
{
if(t != NULL)
{
inorder(t->lc);
printf("%d ",t->data);
inorder(t->rc);
}
}
BST *deleteNode(BST *root,int item)
{
BST *curr = root, *temp = NULL, *parent;
while(curr != NULL)
{
if(curr->data == item)
break;
parent = curr;
if(item > curr->data)
curr = curr->rc;
else
curr = curr->lc;
}
if(curr == NULL)
{
printf("\nDelete Request Failed. Value Not Exists.");
return root;
}
else if(curr->lc == NULL && curr->rc == NULL) // Leaf node (case 1)
{
if(parent == NULL)
root = NULL;
else if(parent->lc == curr)
parent->lc = NULL;
else
parent->rc = NULL;
return root;
}
else if(curr->lc != NULL && curr->rc == NULL) // Only one child (case 2)
{
if (root->data == curr->data)
root = curr->lc;
else if(parent->lc == curr)
parent->lc = curr->lc;
else
parent->rc = curr->lc;
free(curr);
return root;
}
else if(curr->rc != NULL && curr->lc == NULL) // Only one child (case 2)
{
if (root->data == curr->data)
root = curr->rc;
else if(parent->lc == curr)
parent->lc = curr->rc;
else
parent->rc = curr->rc;
free(curr);
return root;
}
else // both child (case 3)
{
parent = curr;
temp = curr->rc;
while(temp->lc != NULL)
{
parent = temp;
temp = temp->lc;
}
curr->data = temp->data;
if(curr == parent)
curr->rc = temp->rc;
else
parent->lc = temp->rc;
free(temp);
return root;
}
}
int main()
{
BST *T = NULL;
int value;
T = insertNode(T, 8);
insertNode(T, 3);
insertNode(T, 10);
insertNode(T, 1);
insertNode(T, 5);
insertNode(T, 9);
printf("Full Tree: ");
inorder(T);
printf("\nAFter Deleting 9(leaf node): ");
T = deleteNode(T, 9);
inorder(T);
printf("\nAFter Deleting 10(node w/ one child): ");
T = deleteNode(T, 10);
inorder(T);
printf("\nAFter Deleting 8(root node): ");
T = deleteNode(T, 8);
inorder(T);
printf("\nAFter Deleting 3(full node): ");
T = deleteNode(T, 3);
inorder(T);
return 0;
}
Output
Full Tree: 1 3 5 8 9 10 AFter Deleting 9(leaf node): 1 3 5 8 10 AFter Deleting 10(node w/ one child): 1 3 5 8 AFter Deleting 8(root node): 1 3 5 AFter Deleting 3(full node): 1 5 -------------------------------- Process exited after 0.4866 seconds with return value 0 Press any key to continue . . .
