-
-
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"; | |
} |
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;
}
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.leftreturn 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
, androot = root->right;
this will not be reflected outside the function,
it should be*root=NULL
, and the function definition should be like thisstruct 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");
It should return temp once deleted root in single child case
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.