One of the complex operation on

we can simply remove the current node for the scenario which shown in the image. the code snippet is given below.

See the sample code snippet below

See the sample code snippet below.

We need to copy the

The sample code snippet is given below.

We need to copy the

**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.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.