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?

Jerry Coffin · Accepted Answer · 2012-06-10 07:10:19Z

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.

edited Jun 10, 2012 at 7:10

answered Jun 10, 2012 at 6:57

Jerry Coffin

494k83 gold badges656 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

greenthunder Over a year ago

Thanks dude, it worked. I think I should repair my code by your advice :)

mawia · Accepted Answer · 2012-06-10 09:44:40Z

0

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.

edited Jun 10, 2012 at 9:44

answered Jun 10, 2012 at 8:44

mawia

9,41715 gold badges50 silver badges57 bronze badges

Collectives™ on Stack Overflow

How to delete subtree in BST C language?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related