CODEWITHSUNDEEP
cdata-structuresbinary-treeroot-node
roberts4
roberts4

Reputation: 1

How to delete root node as part of full tree deletion

I am making a binary search tree that has a function that is deleting all nodes in the tree. When called later on it seems all nodes are being deleted but the root node. Before adding the conditionals to the code below there were also other nodes that weren't getting deleted. That's fixed at this time, but the root node is not getting deleted. Wondering what conditionals should be added or if there's something I'm not understanding about root deletion.

I've tried a simpler solution where no conditionals were used. Program ran fine but after calling a traversal again at the end it seems not everything is actually getting deleted.

TreeNodePtr deleteTree(TreeNodePtr node)
{


    if(node -> left)
    {
        deleteTree(node -> left);
        printf("Deleting node %s \n", node -> left -> data.word);
        free(node -> left);
        node -> left = NULL;
    }

    if(node -> right)
    {
        deleteTree(node -> right);
        printf("Deleting node %s \n", node -> right -> data.word);
        free(node -> right);
        node -> right = NULL;
    }


    if(allocation_count == 1)
    {
        printf("Deleting node %s \n", node -> data.word);
        free(node);
        node = NULL;
    }


    //whenever a node is deleted this decreases by one, when at one  
    //attempt to delete root node
    allocation_count--;

    return node;

}

All of the deletion instances are being printed out, but the root is not actually getting removed from the tree. One node value remains and gets printed out when a traversal is called after the deletion process.

Upvotes: 0

Views: 1697

Answers (2)

Deduplicator
Deduplicator

Reputation: 45704

The code you show is unneccessarily convoluted, hiding subtle issues.
Anyway, it cannot modify the argument passed, as in C all arguments are passed by value.
Considering you return a TreeNode*, the caller is probably responsible for assigning it to the root-pointer.

Also, unless you only ever have at most one tree, using a global like allocationCount for per-tree attributes is a bug.

And finally, what if your tree is empty?

Simplified fixed code:

TreeNode* deleteTree(TreeNode* node) {
    if (!node)
        return 0;
    deleteTree(node->left);
    deleteTree(node->right);
    printf("Deleting node %s\n", node->data.word);
    free(node);
    --allocationCount; // Whatever for. Statistics maybe?
    return 0;
}

Upvotes: 3

Emily
Emily

Reputation: 1096

Your algorithm immediately starts by deleting the left and right subtrees, and does not delete the root node.

Remember that trees are a recursive structure, and each subtree has its own root node. Hence, you should delete node and then recursively call deleteTree on the left and right subtrees.

This should work:

void deleteTree(TreeNodePtr node)
{
    if(node -> left)
    {
        deleteTree(node -> left);
        node -> left = NULL;
    }

    if(node -> right)
    {
        deleteTree(node -> right);
        node -> right = NULL;
    }

    free(node);
}

Upvotes: 2

Related Questions