Delete node from binary search tree

Given a binary search tree and a node, delete node from binary search tree. This is typical programming interview question to check candidates understanding about binary search tree properties and how it can be maintained when a node is either inserted or deleted from BST.
Before deleting a node, three cases needs to be considered

Case 1: If node to be deleted is leaf node.
This case is quite easy to handle: delete node, set the pointer in parent node as NULL (very important step, we usually miss it which leads to dangling pointer and segmentation faults ).

Case 2: If node to be deleted is not leaf and there is only one child.
In this case, copy value of child into currentNode, delete the child and mark appropriate (left or right pointer) of root as NULL.

Case 3:If node has two children
This is one tricky case. First find inorder successor of the node. Replace node to be deleted value with value of inorder successor and then delete inorder successor. Deletion of inorder successor again follow the same problem pattern of deleting original node. Hence the recursion.

Delete node from binary search tree

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

Node * createNode(int value){
Node * newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}

Node * addNode(Node *node, int value){

if(!node) return createNode(value);

if (node->value > value)
else

return node;
}

Node * findMinimum(Node *root){
if(!root)
return NULL;

while(root->left){
root = root->left;
}
return root;
}

Node * deleteNode(Node *root, int key){
if(!root)
return root;

if( root->value > key ){
//Delete node is on the left subtree
root->left = deleteNode( root->left, key);
}
else if ( root->value < key ){
//Delete node is on the left subtree
root->right = deleteNode( root->right, key);
}

if(root->value == key){

if ( !(root->left) ){
/*If there is only one child or there is no child
Get the right child, it may be NULL too.*/
Node *currentNode = root->right;
free(root);
return currentNode;
}
else if ( !( root->right ) ){
/*If there is a left child. Check if there is no right child.
If there is no right child, return the left child. */
Node *currentNode = root->left;
free(root);
return currentNode;
}
/*Case when both children are there.
Get the minimum in right subtree and return that.*/
Node * currentNode = findMinimum(root->right);
//Copy the node value
root->value = currentNode->value;

root->right = deleteNode(root->right, currentNode->value);
}
return  root;
}

void inorder(Node * root){
if(!root) return ;

inorder(root->left);
printf("%d ", root->value);
inorder( root->right);
}
/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

inorder(root);

deleteNode(root, 25);

printf("\n");
inorder(root);

return 0;
}
```

To locate any node in a BST is O(logN) given that tree is not completely skewed where the complexity becomes O(N).

Inorder successor of a node is to be found only when there is right child of node. When there is right child of a node, inorder successor is minimum node in right subtree, hence in the code you see we just find minimum node in right subtree.

Reference : For details how to find inorder successor of a given node in binary search tree, please refer to Inorder successor .