Deletion in binary search tree in C

Question

My linked list structure is

typedef struct ll
{
 int data;
 struct ll *left;
 struct ll *right;
}node;

My function for deleting is

void delete(node **parent,node **root,int n)
{
 if((*root)==NULL) //if tree is empty then return
 {
  printf("No tree\n");
  return;
 }
 else
 {
   if(((*root)->data)==n)
  {
   free(*root);
   return;  // if head is the node to be deleted
  }
  else if(((*root)->data)<n)
  {
   (*parent)=(*root);
   (*root)=(*root)->right;
  }
  else(((*root)->data)>n);
  {
   (*parent)=(*root);
   (*root)=(*root)->left;
  }
   while((*root)!=NULL)
   {
    if(((*root)->data)==n)
    {      
     break;
    }
    (*parent)=(*root);
    if(((*root)->data)>n)
    (*root)=(*root)->left;
    else
    (*root)=(*root)->right;
   }
 }
 if(((*root)->left)==NULL && ((*root)->left)==NULL) //both children are NULL
 {
  del_a(parent,root);
 }
 else if(((*root)->left)==NULL && ((*root)->left)!=NULL)// only one child is NULL
 {
  del_b(parent,root);
 }
 else if(((*root)->left)!=NULL && ((*root)->left)==NULL)// only one child is NULL
 {
  del_b(parent,root);
 }
 else
 {
 del_c(parent,root); //No child is NULL
 }
}

del_a(node **parent,node **root)
{
 if((*parent)->left==(*root))
 {
  free(*root);
  (*parent)->left=NULL;
 }
 else
 {
  free(*root);
  (*parent)->right=NULL;
 }
}

del_b(node **parent,node **root)
{
 if(((*parent)->left)==(*root))
 {
  if(((*root)->left)==NULL)
  {
   (*parent)->left=(*root)->right;
   free(*root);
  }
  else
  {
   (*parent)->left=(*root)->left;
   free(*root);
  }
 }
 else
 {
  if(((*root)->left)==NULL)
  {
   (*parent)->right=(*root)->right;
   free(*root);
  }
  else
  {
   (*parent)->right=(*root)->left;
   free(*root);
  }  
 }
}

del_c(node **parent,node **root)
{
 node *temp=(*root)->right;
 node *prt=(*root);
 while((temp->left)!=NULL)
 {
  prt=temp;
  temp=temp->left;
 }

  (*root)->data=temp->data;

 if((temp->right)==NULL)
 {
  del_a(&prt,&temp);
 }
 else
 {
  del_b(&prt,&temp);
 }

}

I am passing the arguments (where head is the first node)

delete(NULL,&head,n);

The program takes the number n to be deleted but then crashes immediately. What is the problem?

I'm using windows console for running the program.It says 'the program stopped executing' and then prompts for a close — srk
– srk, Commented Nov 26, 2013 at 16:38

Fiddling Bits · Accepted Answer · 2013-11-25 16:49:16Z

2

You're using parent when it has an address of NULL. You must be getting segmentation fault too.

answered Nov 25, 2013 at 16:49

Fiddling Bits

8,9144 gold badges32 silver badges48 bronze badges

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

2 Comments

srk Over a year ago

so what should I pass as the arguments?

Fiddling Bits Over a year ago

parent can't be NULL. Do you have parent defined so you can call you function like this: delete(&parent, &head, n);?

Collectives™ on Stack Overflow

Deletion in binary search tree in C

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related