Reputation: 2882
i am trying to delete a leaf node
from binary search tree, and it is not working for me, i debugged the code and, i can't find the issue. I can see flow is going correct, call reaches to leaf node
address, and then calls free
. But after that when i execute pre-order
traversal i see the value is still there.
Binary tree i created(Its a simple one) -:
10
/ \
6 14
Leaf Node
value to be deleted = 14
;
Before deletion Pre - order
traversal result = 10->6->14
. This is printed on my console.
Code to delete leaf node
-:
// Delete a leaf node
void deleteNode(struct Nodes * root,int value){
// Check if root is null
if (root == NULL) {
return;
}
// If no left and right node present, it's a leaf node. Perform delete.
while (root->left == NULL && root->right == NULL) {
// Check if value at leaf node is same as value to be deleted. If yes, go inside (if).
if (root->info == value) {
printf("Delete the leaf node \n");
printf("delete node address is \n %p",root);
// free the root (which is currently a leaf node)
free(root);
return;
}
}
// keep checking if value to be deleted is on right or left, till a value is found.
if (root->info < value) {
// Ccheck on right
deleteNode(root->right,value);
}else{
// check on left
deleteNode(root->left,value);
}
}
I don't get any errors
, so i am not able to guess root cause.
After deletion Pre - order
traversal result = 10->6->14
. Can anyone help me out? I know i am doing very silly mistake, or my concept is still not crystal clear.Thanks.
Please let me know if any other information is required.
Image of output-: You can see I am on correct value, and the address for same.
Upvotes: 1
Views: 5686
Reputation: 3774
One approach would be to pass the pointer to the parent in the recursive call. Something like this:
void deleteNode(struct Nodes *root, struct Nodes *parent, int value){
// Check if root is null
if (root == NULL) {
return;
}
if ((root->info == value) && (root->left == NULL) && (root->right == NULL)) {
if (parent->left->info == value) {free(parent->left); parent->left = NULL;}
else {free(parent->right); parent->right = NULL;}
}
else if (root->info < value) {
// check on right
deleteNode(root->right,root, value);
}else{
// check on left
deleteNode(root->left,root, value);
}
}
Upvotes: 2
Reputation: 6391
free
means pretty much "I swear I will not use the memory any more, it may be free'd or reallocated arbitrarily".
You are violating that promise. After freeing the memory, you must also forget all references on that address. The parent node still remembers the address where the node used to be, and by chance the memory has not been recycled yet.
You have a typical "use after free" error. If you had allocated another node in between, before traversing again, you would have noticed a memory corruption.
You could add one more parameter to your function which points to the pointer in the parent object. That way you can modify the parent.
Or store a reference back to the parent in the node.
Either works.
Upvotes: 3