Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Last active April 14, 2024 04:05
Show Gist options
  • Save mycodeschool/9465a188248b624afdbf to your computer and use it in GitHub Desktop.
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";
}
@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