Delete node from binary search tree

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 ).
Delete node from binary search tree

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.

Delete node from BST

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 in BST

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.

  • Monil

    the logic when node to be deleted when it has right subtree is incorrect.

  • http://algorithmsandme.in/ Jitendra Sangar

    Agree, only thing we need to do when there is a right child associated, we need to find the minimum in right sub tree and replace the current node with that node. Thanks, I will update the code.