CODEWITHSUNDEEP
cpointers
KChaloux
KChaloux

Reputation: 4028

Nullifying a value from a pointer

I haven't done pointer arithmetic in a long time, so I figured I'd try my hand at C and do a simple Binary Search Tree. I can't get the hang of deletion, however. Something along these lines works as I expect:

typedef struct Node{
    int value;
    struct Node *left;
    struct Node *right;
}Node;

typedef struct Tree{
    struct Node* root;
}Tree;

int main(){
    Tree *tree = createTree(); 

    treeInsert(10, tree);    // Inserts 10 at root
    treeInsert(30, tree);    // Inserts 30 to root->right
    treeInsert(5, tree);     // Inserts 5 to root->left
    treeInsert(7, tree);     // Inserts 7 to root->left->right
    treeInsert(12, tree);    // Inserts 12 to root->right->left

    // Removes Node "7" from the tree successfully
    free(tree->root->left->right);   // Free memory for this node in the tree
    tree->root->left->right = NULL;  // Set the pointer to NULL

    return 0;
}

I'd like to write a nodeDelete(Node *killNode) function to free the memory associated with a node, then point it to NULL, but I find it doesn't work like I expect it to.

int main(){
   // ... snip ...

   Node *kill = tree->root->left->right  // Points kill node to Node "7"
   free(kill);                           // Deallocates memory
   kill = NULL;                          // Points kill to NULL, but keeps 
                                         //   tree->root->left->right **undefined** 
   // ... snip ...
}

I think my problem is that I'm telling it that kill now points to NULL, which disconnects it from the node in the tree and doesn't effect the original node pointer. How can I tell it that I want to point tree->root->left->right to NULL instead of kill? Do I need a pointer-to-a-pointer in this case?

Upvotes: 1

Views: 1096

Answers (2)

Martin B
Martin B

Reputation: 24140

Yes, you need to use a double pointer. You'll also want to make sure you recursively delete any children of the node you're deleting:

void nodeDelete(Node **killNode)
{
    if(!*killNode)
        return;

    // Free child nodes
    nodeDelete((*killNode)->left);
    nodeDelete((*killNode)->right);

    // Free the node itself
    free(*killNode);
    *killNode=NULL;
}

The null-pointer check is intentionally performed right at the beginning -- this prevents you from having to wrap the recursive calls in null-pointer check.

Upvotes: 0

caf
caf

Reputation: 239011

Yes, if you want to delete that node you need to set tree->root->left->right to NULL. This means that you can't just pass the value of that pointer to the deletion function.

You have two options: you can either pass a pointer to the parent of the node to be deleted, along with information about which child to delete:

nodeDelete(Node *parent, int kill_right)
{
    Node *kill;

    if (kill_right) {
        kill = parent->right;
        parent->right = NULL;
    } else {
        kill = parent->left;
        parent->left = NULL;
    }

    free(kill);
}

In this case you'd call nodeDelete(tree->root->left, 1);.

Alternatively you can pass a pointer to the pointer that you want to remove:

nodeDelete(Node **killptr)
{
    free(*killptr);
    *killptr = NULL;
}

In this case you'd call nodeDelete(&tree->root->left->right);.

Upvotes: 2

Related Questions