Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Last active January 22, 2024 10:12
Star You must be signed in to star a gist
Save mycodeschool/9465a188248b624afdbf to your computer and use it in GitHub Desktop.
/* 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";
}
@phongvu009
Copy link

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

@AryanGitHub
Copy link

AryanGitHub commented Feb 5, 2022

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)

@Akash2791-1
Copy link

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;

}

@vinamrgrover
Copy link

vinamrgrover commented Apr 14, 2022

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.

@vinamrgrover
Copy link

vinamrgrover commented Apr 14, 2022

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");

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment