/* 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"; | |
} |
This comment has been minimized.
This comment has been minimized.
I have the same issue. I thought that deleting a node with one child, we are supposed to find the parent, and link the parent to the child of the node to be deleted. You are just making the node to be deleted point to his child, and delete the node. Does that automatically make the parent of the node to be deleted point to the child of the node to be deleted? If so how does that work? Can you please clarify? |
This comment has been minimized.
This comment has been minimized.
to @sidhjhawar and @Merciaugust29, That's why the Delete function has a return statement. It's returning the same node that's being deleted, which is most of the time is NULL. For example, let say we're deleting node 11. A recursive function ended up in node 10, line 20. The root in this context is the node 10 itself. line 20: root(node10)->right = Delete(root->right(node11), 11) Here, the Delete function is called again and the root in this context become node 11. Since node 11 has no child, the logic ends up on line 24. The root is deleted and set to NULL. This NULL value is then returned to the earlier call we had above: back to line 20: root(node10)->right = NULL; So effectively, from node 10 perspective, node 11 is truly gone. You could argue with the same logic for any other cases. |
This comment has been minimized.
This comment has been minimized.
Very Clean and helpful code. Thank You, |
This comment has been minimized.
This comment has been minimized.
May be a small thing. While running the above program i get this error root@runnable:~# g++ /root/main.cpp
/root/main.cpp: In function 'void Inorder(Node*)':
/root/main.cpp:44:26: error: 'printf' was not declared in this scope I think we need to include root@runnable:~# g++ /root/main.cpp
root@runnable:~# /root/a.out
Inorder: 1 3 4 10 11 You can checkout the code in runnable link |
This comment has been minimized.
This comment has been minimized.
Great explanation and elegant code. Thanks a lot. |
This comment has been minimized.
This comment has been minimized.
What need of temp? |
This comment has been minimized.
This comment has been minimized.
HI while i m running the above i m getting error as it is in below link [http://stackoverflow.com/questions/29491024/crash-this-may-be-due-to-a-corruption-of-the-heap](click here) how to resolve plz help me out thanks in advance |
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
Thnaks |
This comment has been minimized.
This comment has been minimized.
shouldn't the second case be like this : |
This comment has been minimized.
This comment has been minimized.
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 comment has been minimized.
This comment has been minimized.
this code is quite very clean to understand,thank you very much ,you did a great job,atleast better than what my lecturer does |
This comment has been minimized.
This comment has been minimized.
i have a doubt.. how the ctrl trasfers to else if to else |
This comment has been minimized.
This comment has been minimized.
good explanation. |
This comment has been minimized.
This comment has been minimized.
In Insert function, data has input as char data type, why? |
This comment has been minimized.
This comment has been minimized.
Let me copy paste the funtion with comments so that u may understand: Node* deleteNode(Node* temp, int data)
} |
This comment has been minimized.
This comment has been minimized.
for making memory free . because that data is not useful for us now. but it is stored in Heap section. |
This comment has been minimized.
This comment has been minimized.
why we assign delete function to root in line 87. |
This comment has been minimized.
This comment has been minimized.
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. I tried this on my end, below is the python version of doing the same. CASE 1: Delete root of the binary tree
|
This comment has been minimized.
This comment has been minimized.
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):
This is what I did to fix it. |
This comment has been minimized.
This comment has been minimized.
Hi paras062, |
This comment has been minimized.
This comment has been minimized.
Hey this is Harshit here. |
This comment has been minimized.
This comment has been minimized.
you have to free the memory |
This comment has been minimized.
This comment has been minimized.
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 |
This comment has been minimized.
This comment has been minimized.
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. |
This comment has been minimized.
This comment has been minimized.
Yes the memory allocate in the heap section must be free. If not deleted then this may lead to program crash or memory leak |
This comment has been minimized.
This comment has been minimized.
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; |
This comment has been minimized.
This comment has been minimized.
I think this is good as it seems logical to me. I am not clear with the source code. |
This comment has been minimized.
This comment has been minimized.
Very clean and clear code. Thanks.. |
This comment has been minimized.
This comment has been minimized.
A small bug, the Case 2 logic should be like this (ignoring delete statements):
The original logic is <3 |
This comment has been minimized.
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