How to delete subtree in BST C language?

Question

I wanna make pop function to delete the node and subtree of the node. Here is my code

void pop(struct data *node,int num)
{
    if(node)
    {
        if(node->num==num)
        {
            pop(node->left,num);
            pop(node->right,num);
            free(node);
            node=NULL;
        }
        else
        {
            if(num> node->num)
                pop(node->right,num);
            else if (num< node->num)
                pop(node->left,num);
        }
    }
}
void pre(struct data *node)
{
    if(node)
    {
        printf("%d ",node->num);
        pre(node->left);
        pre(node->right);
    }
}
void main()
{
    push(&root,37);
    push(&root,20);
    push(&root,45);
    push(&root,5);
    push(&root,15);
    push(&root,40);
    push(&root,50);
    pre(root);
    pop(root,5);
    pre(root);
    getchar();
}

Pre function works well before I use pop. But after I used the pop function, it's break. Could anyone knows where's the mistake?

Answer 1

In pop, you're doing: node=NULL; -- but this only affects the copy of the pointer that was passed to the function, not the pointer in the original tree. Your tree retains the pointer to the data you've now freed. The next time you do much with the tree, you try to dereference that pointer, and things fall down and go boom (at least you hope they do -- even worse, sometimes they might seem to work).

One way to fix this is to pass a double pointer to pop:

void pop(struct data **node, int num) { 

    if ((*node)->num == num)
        // ...
        free(*node);
        *node = NULL;
    }
}

Now you're changing the pointer in the tree instead of changing the copy of it your function received.

This still won't work quite right though -- you're depending on pop(child, num); to destroy the sub-trees of the current node, but unless their num is set to the same value, they won't delete anything, just travel down the tree looking for a node with a matching num.

You probably want one function to walk the tree finding the node you care about, then a second one that walks the tree starting from a designated node, and (unconditionally) destroys that node and its sub-trees.

Answer 2

Well your pop function should be like this:

struct data* pop(struct data *node,int num)
{
  struct data* temp=null;
if(node)
{
    if(node->num==num)
    {
      if(node->left)
        pop(node->left,node->left->num);
      if(node->right)
        pop(node->right,node->right->num);
      free(node);
    }
    else
    {
        if(num> node->num)
            temp=pop(node->right,num);
        else if (num< node->num)
            temp=pop(node->left,num);

       if(node->right==temp)
        node->right=null;
       else if(node->left==temp)
        node->left=null;
       return temp;
    }
 }
return node;
}

This will work as far as you have the logic to nullify the root of the tree from where it is being called, if the desired node tuned out to be root of the tree.