Home » Data Structure

Deletion in Binary Search Tree (BST)

Deletion in Binary Search Tree: Here, we will learn how to delete a Node in Binary Search Tree. In this article you will find algorithm, example in C++. Submitted by Abhishek Jain, on July 29, 2017

Suppose, T is a binary Search tree, and an ITEM of information is given. This section gives an algorithm which deletes ITEM from the tree T.

The deletion operation first uses Search () to check for node N which contains ITEM is present in the tree or not. The way N is deleted from the tree depends primarily on the number of children of node N. There are three cases:

Case I:
N (node) has no children. Then N is deleted from T by simply replacing the location of N in the parent node by the NULL pointer.

Reference: algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

Case II:
N has exactly one child. Then N is deleted from T by simply replacing the location of N in parent node by the location of the only child of N.

Reference: algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

Case III:
N has two children. Then N is deleted from T by replacing its location in parent node with its selected child node, selection is possible in two different ways:

1. Find the in-order successor of node N (smallest node in the right subtree of the node N).
2. Find the in-order predecessor of Node N (largest node in the left subtree of the node N).

Note: To better understand about in-order successor and in-order predecessor please go through the link: (Find In-Order Successor and predecessor in Binary Search Tree).

Reference: algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

Consider the C++ program:

#include<iostream>
using namespace std;

bool c=false;

struct node
{
	int data;
	node* left;
	node* right;
};

struct node* getNode(int data)
{
	node* newNode=new node();
	newNode->data=data;
	newNode->left=NULL;
	newNode->right=NULL;
	return newNode;
}

void inorder(struct node* root)
{
    if (root != NULL)
     {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

node* findMin(node*root)
{
    while(root->left!=NULL)
    {
        root=root->left;
    }
    return root;
}

struct node* Insert(struct node* root, int data)
{
	if (root == NULL)
		return getNode(data);

	if (data < root->data)
		root->left  = Insert(root->left, data);
	else if (data > root->data)
		root->right = Insert(root->right, data);

	return root;
}

bool Search(node*root,int value)
{ 
	if(root==NULL)
		return false;
	else if(root->data == value)
	{
		return true;
	}
	else if(value < root-> data)
		Search(root->left,value);
	else if(value > root->data)
		Search(root->right,value);
}


node* Delete( node* root,int value)
{ 
	c=Search(root,value);
	if(root==NULL)
		return root;
	else if(value< root->data)
	{
		root->left= Delete(root->left,value);
	}
	else if(value> root->data)
	{
		root->right= Delete(root->right,value);
	}
	
	// Node deletion
	else
	{
		//case 1: Leaf Node
		if(root->left==NULL&&root->right==NULL)
		{
			delete root;
			root=NULL;
			return root;
		}
		//case 2: one child
		else if(root->left==NULL)
		{
			struct node* temp=root;
			root=root->right;
			delete temp;
			return root;
		}
		else if(root->right==NULL)
		{
			struct node* temp=root;
			root=root->left;
			delete temp;
			return root;
		}
		//case 3: 2 child
		else
		{
			struct node*temp=findMin(root->right);
			root->data=temp->data;
			root->right=Delete(root->right,temp->data);
		}
	}
	return root;

}


int main()
{  
	node* root=NULL;
	root=Insert(root,20);
	Insert(root,15);
	Insert(root,25);
	Insert(root,18);
	Insert(root,10);
	Insert(root,16);
	Insert(root,19);
	Insert(root,17);

	cout<<"Before Deletion: "<<endl;
	cout<<"Inorder: ";
	inorder(root);
	cout<<endl<<endl;

	Delete(root,15);

	if(c)
	{   
		cout<<"Node Deleted"<<endl;
		cout<<"\nAfter Deletion: "<<endl;
		cout<<"Inorder: ";
		inorder(root);
		cout<<endl;
	}
	else
		cout<<"Node Not Found"<<endl;

	return 0;

}

Output

Before Deletion: 
Inorder: 10 15 16 17 18 19 20 25
Node Deleted
After Deletion:
Inorder: 10 16 17 18 19 20 25