BSTDeletion_CPP.cpp

/* Deleting a node from Binary search tree */
#include<iostream>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};
//Function to find minimum in a tree. 
Node* FindMin(Node* root)
{
	while(root->left != NULL) root = root->left;
	return root;
}

// Function to search a delete a value from tree.
struct Node* Delete(struct Node *root, int data) {
	if(root == NULL) return root; 
	else if(data < root->data) root->left = Delete(root->left,data);
	else if (data > root->data) root->right = Delete(root->right,data);
	// Wohoo... I found you, Get ready to be deleted	
	else {
		// Case 1:  No child
		if(root->left == NULL && root->right == NULL) { 
			delete root;
			root = NULL;
		}
		//Case 2: One child 
		else if(root->left == NULL) {
			struct Node *temp = root;
			root = root->right;
			delete temp;
		}
		else if(root->right == NULL) {
			struct Node *temp = root;
			root = root->left;
			delete temp;
		}
		// case 3: 2 children
		else { 
			struct Node *temp = FindMin(root->right);
			root->data = temp->data;
			root->right = Delete(root->right,temp->data);
		}
	}
	return root;
}
 
//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;
 
	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}
 
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else 
		root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); root = Insert(root,10);
	root = Insert(root,3); root = Insert(root,4); 
	root = Insert(root,1); root = Insert(root,11);

	// Deleting node with value 5, change this value to test other cases
	root = Delete(root,5);

	//Print Nodes in Inorder
	cout<<"Inorder: ";
	Inorder(root);
	cout<<"\n";
}

For everyone who are not getting how the link between the parent of deleted node and and child of deleted node is maintainted. You can easily get it just by looking where the return value of each recursion is going.

this code is quite very clean to understand,thank you very much ,you did a great job,atleast better than what my lecturer does

i have a doubt.. how the ctrl trasfers to else if to else

good explanation.

In Insert function, data has input as char data type, why?

Hi, How are you making sure that once the node to be is deleted is deleted and the link to its parent is still maintained now between the child of the node deleted and its parent ?
More specifically,
else if(root->left == NULL) {
struct Node *temp = root;
root = root->right;
delete temp;
}

After deleting the temp, what about the link between temp's parent and current root ? I am little confused here.
Please explain if I am wrong.
Thanks,
Sidharth

Let me copy paste the funtion with comments so that u may understand:

Node* deleteNode(Node* temp, int data)
{
(temp)? std::cout<<"\nIn deleteNode temp->data = " <data : std::cout<<"\nIn deleteNode temp = NULL" ;
if(temp == NULL)
{
std::cout<<"It's NULL";
return temp;
}
else if( data < temp->data)
{
std::cout<<"\n Data to be delted is in left of : " << temp->data << ", so sending next left node ";
temp->left = deleteNode(temp->left, data); //Assign to temp->left because u are sure now u r not deleting current node but in left of current. temp->left will be parent of what deleteNode() returns when stack unwinds
(temp->left) ? std::cout<<"\nReturned temp->left Node: " <left->data : std::cout<<"\nReturned temp->left = NULL";
}
else if(data > temp->data)
{ std::cout<<"\n Data to be delted is in right of : " << temp->data << ", so sending next right node ";
temp->right = deleteNode(temp->right, data); //Assign to temp->right because u are sure now u r not deleting current node but in right of current. temp->right will be parent of what deleteNode() returns when stack unwinds
(temp->right) ? std::cout<<"\nReturned temp->right Node: " <right->data : std::cout<<"\nReturned temp->right = NULL";
}
else //found data to be deleted
{
Node* current = temp; //for clarity
if(current->left == NULL && current->right == NULL) // If no children
{
delete current;
temp = NULL; // return NULL to be linked to previous parent's left or right in previous "else if" when stack unwinds
std::cout<<"\n No children";
}
//Node to be deleted has left or right or both childred
else if(current->left == NULL)
{
temp = current->right;
delete current; // return current->right to be linked to previous parent's left or right in previous "else if" when stack unwinds, U dont need to track parent in recursion as parent will be there when current recursion unwinds to previous
std::cout<<"\n Has right children";
}
else if(current->right == NULL)
{
temp = current->left;
delete current; // return current->left to be linked to previous parent's left or right in previous "else if" when stack unwinds, U dont need to track parent in recursion as parent will be there when current recursion unwinds to previous
std::cout<<"\n Has left children";
}
else//if left and right children
{
std::cout<<"\n Has left and right children";
Node* minNodeInRight = findMinNode(current->right); //Find min node in right of current node, and that min node will be deleted in future.
std::cout<<"\n Min Node found to be deleted is " << minNodeInRight->data;
current->data = minNodeInRight->data; //Copy min node data here and dont delete current but delete the found node in right of current

		//current->right = deleteNode(minNodeInRight->right, minNodeInRight->data); // U cant pass minNodeInRight->right as argument becoz its much below current node, if u send it link with parent will be broken, 
		//U need to traverse from Current node until u find  minNodeInRight->data
		current->right = deleteNode(current->right, minNodeInRight->data);	//Assign to current->right because u are sure now u r not deleting current node but in right of current.	
					
	}
	
}	
(temp) ? std::cout<<"\n END OF DELTE, returning Node: " <<temp->data : std::cout<<"\nReturning temp = NULL";
return temp;

}

What need of temp?
Isn't it enough
root=root->left
for the case 2

for making memory free . because that data is not useful for us now. but it is stored in Heap section.

why we assign delete function to root in line 87.
it is necessary?

Looks like it fail if you try to delete 12 from the BST, as 12 is equal to root.data, and we don't have condition to handle when data = root.data.
Please have a look.
We have condition to check if data > root.data or data < root.data, what missing is data = root.data

I tried this on my end, below is the python version of doing the same.

CASE 1: Delete root of the binary tree

elif (data == root.data):
    temp = root
    newRoot = root.left
    root = root.left


    # Move current root to the end of right most node of the left subtree
    while(root.right != None):
        root = root.right


    if root.right == None:
        root.right = temp.right


    del temp, root
    return newRoot

There is another issue with the code, in your example you've been deleting elements from the right sub tree, if you try to delete from left subtree, your FindMin function will fail.

def minValue(node, data):
current = node
if (data < node.data):
# loop down to find the right most leaf
while(current.right is not None):
current = current.right
elif (data > node.data):
# loop down to find the left most leaf
while(current.left is not None):
current = current.left

return current.data

This is what I did to fix it.

Hi paras062,
we don't need to make that change.The code is similar to search element in a binary tree ie element can be in a left sub tree or right sub tree,all FindMin function does is to find min element in a right sub tree.I executed this code and it works fine.

Hey this is Harshit here.
I just wanted to know if we could directly update the data of root by making a function findmin which returns the integral value of the minimum element of the right subtree. I tried to do it but my final output after deleting some element is coming out exactly the same.
Would appreciate it if anyone could tell me what is wrong in the code;
MY UPDATED CODES.
else // the updated case.
{
root->data=findmin(root->right);
root->right=deleteNode(root->right, root->data);
return root;
}
int findmin(bnode *root) //the findmin function
{
if(root==NULL)
return -1;
else
{
bnode *temp;
temp=root;
while(temp->left!=NULL)
temp=temp->left;
return temp->data;
}
}

What need of temp?
Isn't it enough
root=root->left
for the case 2

you have to free the memory

shouldn't the second case be like this :
else if(root->right==NULL){
Node* temp=root->left;
delete root;
root=temp;
}

You must delete the temp as it is holding the address of the root in the memory. And at the last delete the root for deletion of the allocation of the root node in the heap

What need of temp?
Isn't it enough
root=root->left
for the case 2

you have to free the memory

As root is the local variable this might give error. So it is better to store the address in temporary variable and then delete it.

why we assign delete function to root in line 87.
it is necessary?

Yes the memory allocate in the heap section must be free. If not deleted then this may lead to program crash or memory leak

What need of temp?
Isn't it enough
root=root->left
for the case 2

root = root.left will just give attachment with its left pointer but here temp is referring to a minimum in the right subtree of the root;

shouldn't the second case be like this :
else if(root->right==NULL){
Node* temp=root->left;
delete root;
root=temp;
}

I think this is good as it seems logical to me. I am not clear with the source code.
And what will be the code of findMin??

Very clean and clear code. Thanks..

A small bug, the Case 2 logic should be like this (ignoring delete statements):

             //Case 1 node has no children
            if (root.left == null && root.right == null) {
                root = null; 
            }
            // Case 2 Only one child
            else if (root.left != null && root.right == null) {
                root = root.left;
            } else if (root.right != null && root.left == null) {
                root = root.right;
            }
            //Case 3 Both the child are present
            else {

The original logic is <3

I can't seem to delete the root node, if I did it breaks the link in the right sub tree.

#include<iostream>
#include<sstream>
struct node
{
    int data;
    node *left,*right;
};

class bst
{
    node *root;
    public:
    bst()
    {
        root=nullptr;
    }
    node* addNode(node *root,int info)
    {
        if(root==nullptr)
        {
            root=new node;
            root->data=info;
            root->left=nullptr;
            root->right=nullptr;
            std::cout<<"Inserted "<<root->data<<"\n";
            return root;
        }
        else if(info==root->data)
        {
            std::cout<<"Element already exists\n";
            return root;
        }
        else if(info<root->data)
        {
            root->left=addNode(root->left,info);
        }
        else
        {
            root->right=addNode(root->right,info);
        }
        return root;
    }
    void insert()
    {
        std::string s;
        int i;
        do
        {
            std::cout<<"Enter q to quit\n";
            std::cout<<"Enter a unique number : ";
            std::cin>>s;
            if(s=="q")
            {
                std::cout<<"Exited\n";
                return;
            }
            std::stringstream int_str(s);
            int_str>>i;
            root=addNode(root,i);
        }while(true);
    }
    void look(node* root,int info)
    {
        if(root==nullptr)
        {
            std::cout<<"Node not found\n";
        }
        else if(info==root->data)
        {
            std::cout<<"Node found containing "<<info<<"\n";
        }
        else if(info<root->data)
        {
            look(root->left,info);
        }
        else
        {
            look(root->right,info);
        }
    }
    void search()
    {
        int i;
        std::string s;
        do
        {
            std::cout<<"Enter q to quit\n";
            std::cout<<"Enter a number to search  : ";
            std::cin>>s;
            if(s=="q")
            {
                std::cout<<"Exited\n";
                return;
            }
            std::stringstream int_str(s);
            int_str>>i;
            look(root,i);
        }while(true);
    }
    node* findMin(node *root)
    {
        while(root->left!=nullptr)
        { 
		root=root->left;
        }
	return root;
    }
    node* remove(node* root,int info)
    {
        //first search the node
        if(root==nullptr)
        {
            std::cout<<"Not found\n";
            return root;
        }
        else if(info<root->data)
        {
            root->left=remove(root->left,info);
        }
        else if(info>root->data)
        {
            root->right=remove(root->left,info);
        }
        //found the element
        else
        {
            //it has no child
            if(root->left==nullptr && root->right==nullptr)
            {
                delete root;
                std::cout<<"Deleted "<<root->data<<"\n";
                return root;
            }
            //it has one child(right)
            else if(root->left==nullptr)
            {
                node* tmp=root->right;
                delete root;
                std::cout<<"Deleted "<<root->data<<"\n";
                return tmp;
            }
            //it has one child(left)
            else if(root->right==nullptr)
            {
                node* tmp=root->left;
                delete root;
                std::cout<<"Deleted "<<root->data<<"\n";
                return tmp;
            }
            //it has two children
            else
            {
                node* tmp=findMin(root);
                root->data=tmp->data;
                root->right=remove(root->right,tmp->data);
            }
        }
        return root;
    }
    void del()
    {
        int i;
        std::string s;
        do
        {
            std::cout<<"Enter q to quit\n";
            std::cout<<"Enter a number = ";
            std::cin>>s;
            if(s=="q")
            {
                std::cout<<"Exited\n";
                return;
            }
            std::stringstream int_str(s);
            int_str>>i;
            root=remove(root,i);
        }while(true);
    }
};
int main()
{
    bst myt;
    myt.insert();
    myt.search();
    myt.del();
    myt.search();
    return 0;
}

@snake-jazz

delete root;
std::cout<<"Deleted "<<root->data<<"\n";

Access to already deleted object

@snake-jazz

delete root;
std::cout<<"Deleted "<<root->data<<"\n";

Access to already deleted object

Hey, thanks for replying to my post. Actually I've moved to Java so I'm practicing data structures using Java, still appreciate it.

Hello All, why do we need to

Node* FindMin(Node* root){ while(root->left != NULL) root = root->left; return root;}

find Min and use of Inorder here when we have already used it in delete Function.? I have a doubt on this.?
can anybody help me here.? And one more mistake is char data is used instead of integer(int data). so kindly change it.?

What need of temp?
Isn't it enough
root=root->left
for the case 2

There is another issue with the code, in your example you've been deleting elements from the right sub tree, if you try to delete from left subtree, your FindMin function will fail.

def minValue(node, data):
current = node
if (data < node.data):

loop down to find the right most leaf

while(current.right is not None):
current = current.right
elif (data > node.data):

loop down to find the left most leaf

while(current.left is not None):
current = current.left

return current.data

This is what I did to fix it.

We need to FindMax in order to delete from left subtree as Max from left subtree would be Inorder Predecesor

Hello All, why do we need to

Node* FindMin(Node* root){ while(root->left != NULL) root = root->left; return root;}
find Min and use of Inorder here when we have already used it in delete Function.? I have a doubt on this.? can anybody help me here.? And one more mistake is char data is used instead of integer(int data). so kindly change it.?

Inorder function to print the tree in order list like this : 1 3 4 5 10 11

in the code given by mycodeschool, there is a logical bug, which can cause a Segmentation Error
root=NULL, and root = root->right; this will not be reflected outside the function,
it should be *root=NULL, and the function definition should be like this struct Node* Delete(struct Node **root, int data)

my approach without recursive (gfg practice):-

void delLeafnode(Node *cur, Node *prev, int X)
{
if(Xdata) prev->left = NULL;
else prev->right = NULL;
}

void deloneNode(Node *cur, Node *prev, int X)
{
if(Xdata)
{
if(cur->left) prev->left = cur->left;
else prev->left = cur->right;
}
else
{
if(cur->left) prev->right = cur->left;
else prev->right = cur->right;
}

}

Node *findmin(Node *root, int X)
{
Node *cur = root->right;
Node *prev = root;
Node *temp;
while(cur!=NULL)
{
if(!cur->left)
{
temp = cur;
if(!cur->left && !cur->right) delLeafnode(cur, prev, X) ;
else if(!cur->left || !cur->right) deloneNode(cur, prev, X);
}
prev = cur;
cur = cur->left;
}
return temp;
}

Node *deleteNode(Node *root, int X) {
Node *cur = root;
Node *prev = NULL;

if(root->data==X && (!root || (!root->left && !root->right))) return NULL;
while(cur!=NULL)
{
    if(cur->data == X)
    {
        if(!cur->left && !cur->right)
        {
            delLeafnode(cur, prev, X);
        }
        
        else if(!cur->left || !cur->right)
        {
            deloneNode(cur, prev, X);
        }
        
        else if(cur->left && cur->right)
        {
            Node *node = findmin(cur, X);
            cur->data = node->data;
        }
    }
    
    prev = cur;
    if(X<cur->data) cur = cur->left;
    else cur = cur->right;
}
return root;

}

in the code given by mycodeschool, there is a logical bug, which can cause a Segmentation Error
root=NULL, and root = root->right; this will not be reflected outside the function,
it should be *root=NULL, and the function definition should be like this struct Node* Delete(struct Node **root, int data)

How this will not be reflected outside the function if he has equated the function to the original root variable by root = Delete(root,5);?
By using pointer to a pointer you are creating a mess for yourself, nothing else.
Better check this with the Search_Node function.

Hey, I just want everyone to know that after Deleting a node from a BST, better check if the node is present or not by the Search_Node Function. Call the Search_Node function in the main function and check if the value returned by the Search_Node function is true or false.
Here is the Definition:
bool Search_Node(BstNode *root, int data)
{
if(root==NULL)
return false;
if(data==root->data)
return true;
else if(data>root->data)
return Search_Node(root->right, data);
else
return Search_Node(root->left, data);
}

Here's how you can check:
if(Search_Node(root, 20)==true) // here 20 is the data for the deleted node
printf("FOUND\n");
else
printf("NOT FOUND\n");