CODEWITHSUNDEEP
cdata-structuresbinary-search-tree
Tushar Sharma
Tushar Sharma

Reputation: 2882

Delete a leaf node in binary tree

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.

enter image description here

Upvotes: 1

Views: 5686

Answers (2)

babon
babon

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

Ext3h
Ext3h

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

Related Questions