1

I am trying to delete the leaf nodes in a BST which I have created non-recursively. The problem is when I am trying to delete the leaf node I hit a segmentation fault and I have no clue as to why its happening. I believe the code which I have commented is causing the problem. Is the idea of deleting that node wrong or are there any other ways of deleting any node from the BST ?

     #include <stdio.h>
     #include <stdlib.h>

      struct BSTnode
    {
     int data;
     struct BSTnode *left,*right,*parent;

    };

     typedef struct BSTnode node;

     void insert(node **root,int val)
    {
     node *ptr,*newptr;

     newptr=(node *)malloc(sizeof(node));
     newptr->left=NULL;
     newptr->right=NULL;
     newptr->parent=NULL;
     newptr->data=val;

     if((*root)==NULL)
    {
     (*root)=newptr;
     return;
    } 

     ptr=(*root);  

     while(ptr!=NULL && ptr->data!=val)
    {
      if(ptr->data >val )
     {
       if(ptr->left!=NULL)
        ptr=ptr->left;
       else
      {
       ptr->left=newptr;
       newptr->parent=ptr;
       break;
      }
    } 
     else
    {
      if(ptr->right!=NULL)
       ptr=ptr->right;
      else
     {
       ptr->right=newptr;
       newptr->parent=ptr;
       break;
      }
    }
   }

  }

    void deleteLeaf(node **root)
  {

      node *leafParent=NULL;

      if((*root)->left!=NULL)
       deleteLeaf(&((*root)->left));

      if((*root)->right!=NULL)
       deleteLeaf(&((*root)->right));


      if((*root)->left==NULL && (*root)->right==NULL)
     {

      /*  leafParent=(*root)->parent;

          if(leafParent->left==(*root))
           leafParent->left=NULL;
          else
           leafParent->right=NULL;
      */

          free(*root);
        }
      }

 void inorder(node *root)
{
  if(root->left!=NULL)
   inorder(root->left);

  printf(" %d ", root->data);

  if(root->right!=NULL)
   inorder(root->right);
}

 main()
{
 node *root=NULL;
 int i,n,val;

 printf("\n How many elements ?");
 scanf("%d",&n);

 for(i=0;i<n;++i)
{
 scanf("%d",&val);
 insert(&root,val);

}

 printf("\n Inorder traversal : ");
 inorder(root);

 deleteLeaf(&root);
 printf("\n Inorder traversal : ");
 inorder(root);
}

2 Answers 2

0

Indeed there are cases in the function deleteLeaf where the (commented out) leafParent is NULL, and then as soon as you dereference it with leafParent->left, it seg faults. So you need to put a check in there as follows:

    leafParent=(*root)->parent;
    if (leafParent)
    {
        if(leafParent->left==(*root))
        {
            leafParent->left=NULL;
        }
        else
        {
            leafParent->right=NULL;
        }
    }

This will prevent the seg fault, but I am not clear if the function will end up doing what you want it to do... In other words your logic might still need some tweaking to get it to just delete the leaf nodes (if that is what you are attempting to do).

0

I believe you are not really deleting just the leaves - you are recursively deleting the whole tree: for each node you first you delete the leaves and then check whether it is a leaf ((left == NULL) && (right == NULL)) - which it obviously is since you just deleted its descendants - and then delete it.

The first problem is, as Chris quickly pointed out, that you are not checking that leafParent can become NULL. Either check for that or set parent to itself for the root node so that you don't dereference NULL. The other (imho worse) problem is that you are not invalidating pointers once you free the memory - good habit is to set pointers to NULL as soon as you free them. If you don't do checks later on you can segfault but won't silently corrupt memory by using the pointer later on when the chunk of memory might be allocated by some other structure. You can even write a wrapper to do that for you (and it can also check for attempts to free a NULL pointer, which is actually a valid operation that just silently does nothing - at least on some platforms). In this particular case, once you finish deleting the whole tree (as that is what really happens), you still have pointer to the removed root node inside of main() - and you use it immediately.

As a nitpicking side-note, in code it is either int main(void) { ... } or int main(int argc, int **argv) { ... } not just main(). :-)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.