CODEWITHSUNDEEP
cmallocbinary-tree
Steven Underhill
Steven Underhill

Reputation: 21

How to correctly deallocate structure from memory

I have a dynamic data structure which looks like this:

struct tree_node {
    int y;
    int x;
    struct tree_node *left;
    struct tree_node *right;
    struct tree_node *parent;
};

The structure is a node of a binary tree, with the addition that each node also points to its parent. Now, using the classical method of adding nodes to the binary tree using malloc() I can populate the binary tree easily. However, I am having trouble deallocating the binary tree from memory.

Usually, to remove nodes from the binary tree you perform a post-order traversal and then free each node like this:

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    printf("Deleting node with values [%d][%d]\n", node->y , node-> x);

    free(node -> left);
    free(node -> right);
    free(node -> parent);
    free(node);
    printf("\nNode deleted");
}

However, when I run the above function it does not deallocate the binary tree from memory. When I run the function, it deallocates one leaf and then when it tries to delete the next node it gets stuck in an endless loop and my computer either crashes or the program exits with a non-descriptive error.

The output in the terminal is the following:

Deleting node with values [11][4]
Node deleted
Deleting node with values [7739840][0]

So the terminal shows that it deletes the first leaf, and then it tries to fetch the values from the next node but it cannot (which is why it displays 7739840). Then it gets stuck in an endless loop since it does not print "Node deleted".

How can I correctly deallocate the memory? Does it have to do with the way my node is built?

Upvotes: 2

Views: 142

Answers (3)

JimmysPavlou
JimmysPavlou

Reputation: 27

This is happening because you are freeing the same node multiple times.

To delete a binary search tree you have to do something like this.

void bst_destroy(BSTNode node) {
    if (node == NULL) {
        return;
    }

    bst_destroy(node->left);
    bst_destroy(node->right);

    free(node);
}

Basically to delete a binary search tree you have to delete the leaves of the tree one by one so you don't end up deleting parent nodes you might have to visit again (which you will have to do if you are using recursion).

Upvotes: 0

dbush
dbush

Reputation: 224352

You're deallocating nodes multiple times.

When you delete a given node, after deleteTree(node->left) is called the left node has already been freed, so it doesn't need to be freed again. So remove free(node->left).

The current node has also been freed because free(node->parent) was called in that function, so any further reads of node access freed memory. So remove free(node->parent).

And similarly to the call to deleteTree(node->left), calling deleteTree(node->right) already frees the right node, so remove the call to free(node->right).

So now you're left with:

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    printf("Deleting node with values [%d][%d]\n", node->y , node-> x);

    free(node);
    printf("\nNode deleted");
}

In short, each node is responsible for cleaning itself up.

Upvotes: 5

Zakk
Zakk

Reputation: 2063

The correct way of deallocating all the nodes from your tree structure looks like this:

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    free(node);
}

Upvotes: 5

Related Questions