One of the complex operation on binary search tree is deleting a node. Insertion is easy by calling recursive insertion. But deletion wont work with recursive. We need to handle different cases for deletinga node. Lets see all possible cases one by one in detail.
Finding the node to delete: First step for deleting a node is to find the node in the tree. If the node is not in the tree, no need of delete. So below is the code snippet for finding the node.
Case1: Current node has zero child's as shown in below image. current node is either left or right child of the prev node.
we can simply remove the current node for the scenario which shown in the image. the code snippet is given below.
Case2: Current node has one child either left or right.
Case2-A: Current node with right child as shown in the below image. There are two possibilities as shown in the below image.
See the sample code snippet below
Case2-B: Current node with left child as shown in the below image. There are two possibilities as shown in the below image.
See the sample code snippet below.
Case 3: Current node with two child's as shown in the below image. There are again four possibilities as shown in the below images. These four cases we need to handle carefully.
Case3-A: If the current node right child has no children. The scenario is shown below.
We need to copy the tmp node data to current node and delete the tmp node.
Case3-B: If the current node has left child. This is the tricky one. If the left child is available (we can ignore whether right child is available or not), we need to find the smallest element in the left side and replace it with current node and delete the smallest node. To find the smallest element, just find the left most node from the tmp node. This is to satisfy the binary search tree property.
The sample code snippet is given below.
Case3-C: If the current node has only right child. The scenario is as shown in the image.
We need to copy the tmp data to current node and delete the tmp node. the code snippet is given below.
Finding the node to delete: First step for deleting a node is to find the node in the tree. If the node is not in the tree, no need of delete. So below is the code snippet for finding the node.
current = root;
while(current!=NULL)
{
if(current->info == key)
{
found = 1;
break;
}
else
{
prev = current;
if(current->info >= key)
current = current->left;
else
current = current->right;
}
}
Here we are maintaining two pointers prev and current, so that we can have the link to maintain. After finding the node to delete, there are four possible cases. See one by one.Case1: Current node has zero child's as shown in below image. current node is either left or right child of the prev node.
we can simply remove the current node for the scenario which shown in the image. the code snippet is given below.
if((current->left == NULL) && (current->right == NULL))
{
if(prev->left == current)
prev->left = NULL;
else
prev->right = NULL;
free(current);
}
Case2: Current node has one child either left or right.
Case2-A: Current node with right child as shown in the below image. There are two possibilities as shown in the below image.
See the sample code snippet below
if(current->left == NULL && current->right != NULL)
{
if(prev->left == current)
prev->left = current->right;
else
prev->right = current->right;
free (current);
}
Case2-B: Current node with left child as shown in the below image. There are two possibilities as shown in the below image.
See the sample code snippet below.
if(current->right == NULL && current->left!=NULL)
{
if(prev->left = current)
prev->left = current->left;
else
prev->right = current->left;
free(current);
}
Case 3: Current node with two child's as shown in the below image. There are again four possibilities as shown in the below images. These four cases we need to handle carefully.
Case3-A: If the current node right child has no children. The scenario is shown below.
We need to copy the tmp node data to current node and delete the tmp node.
Case3-B: If the current node has left child. This is the tricky one. If the left child is available (we can ignore whether right child is available or not), we need to find the smallest element in the left side and replace it with current node and delete the smallest node. To find the smallest element, just find the left most node from the tmp node. This is to satisfy the binary search tree property.
The sample code snippet is given below.
Case3-C: If the current node has only right child. The scenario is as shown in the image.
We need to copy the tmp data to current node and delete the tmp node. the code snippet is given below.
if(current->left != NULL && current->right != NULL)
{
struct bst *tmp = current->right;
//case3-A
if(tmp->left == NULL && tmp->right == NULL)
{
current->info = tmp->info;
//current = tmp;
free(tmp);
current->right = NULL;
}
//case3-B
else if(current->right->left != NULL)
{
struct bst *left_current = current->right;
struct bst *left_current_prev = current->right->left;
while(left_current->left != NULL)
{
left_current_prev = left_current;
left_current = left_current->left;
}
current->info = left_current->info;
free(left_current);
left_current_prev->left = NULL;
}
//case3-C
else
{
struct bst *temp;
temp = current->right;
current->info = temp->info;
current->right = temp->right;
free(temp);
}
}
Click here for the complete Binary search tree C program. 
