**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) node->left = addNode(node->left, value); else node->right = addNode(node->right, value); 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 root = addNode(root,30); root = addNode(root,20); root = addNode(root,15); root = addNode(root,25); root = addNode(root,40); root = addNode(root,37); root = addNode(root,45); 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 .

Please share if there is something missing or wrong. If you are interested in contributing to website, please contact us.