deletion of a node in binary tree passing node by reference only

Question

I am trying to delete a binary tree, my program work as follows:

(1) It reads the number of nodes to be created in tree.

(2) It reads all those nodes.

(3) It print the tree formed by those nodes.

(4) It reads the node to be delete at terminal.

Until here everything works fine but when i try to delete the desired node then it gives segmentation fault error.

Note: I have to pass the root by reference only (thats why i have kept two pointers for root in delete_tree_node(int delete_val, node **root)).

My approach to do so is: I call recursively the function delete_tree_node() by left and right child in order to traverse the tree until i get the value of node equal to the value the node which user wants to delete.And once if i get that place then i free() that node.

My code to achieve this is: (which gives segmentation problem):

delete_tree_node(int delete_val, node  **root)//two "**" because i call by reference in function call    
{
 node*temp1;
 temp1=(*root);
if(delete_val==(*root)->freq)
   {    
     free((*root));    
     temp1=temp1->left;    
     (*root)=temp1;     
   }   

if(delete_val<temp1->freq)    
   { 
     delete_tree_node(delete_val,&temp1->left);    
   }
if(delete_val>temp1->freq)    
   {
     delete_tree_node(delete_val,&temp1->right);
   }    
}

It's function call is :

delete_tree_node(delete_val, & head);//I give reference

Could some one help me in knowing :

(1) Why it gives segmentation error.

(2) Is my logic is correct to delete the desired node ?, If not then could you please give me a piece of code to make as reference?

Answer 1

Why it gives segmentation fault?

Because you free the memory pointed by *root before you try to access the same memory in temp1->left.

Let's look at things closely :-

temp1 = (*root)

temp1 now holds the same memory address as (*root), i.e. both are some numbers that point to the same address. For the sake of clarity, let's assume that number to be '6'. So, both of them point to the memory address '6'. Note, they are not equal to the value at that address, but are just pointing to that.

Now, free((*root)); tells the system that you are freeing the memory location pointed to by (*root), which in this case is 6. Once you free the memory, you lose access permission to that memory and next time you request it (through temp1->left), you get the segmentation fault.

I hope that clarifies what is causing the segmentation fault.

A cursory glance tells me that you could fix this by freeing (*root) at the end. In fact, the recursive call would be clearer that way, since you can describe it through this pseudo-code :-

delete left subtree
delete right subtree
delete root

I will not delve into the correctness of the logic as it appears to be a homework problem, and it'd be advisable that you solve that part yourself.

Answer 2

 temp1=(*root); // copying  the memory address of node to temp1   
 free((*root));    // your freeing the memory here of the node 
 temp1=temp1->left;    // the memory your accessing is already free'd hence segmentation fault occurs

try interchanging the two statements .

temp1=temp1->left;
free((*root));

regarding the reference for logic check here

Answer 3

You cannot free the node and then access it. Try to move the free after the temp1=temp1->left. Also, you must return once you found the correct node or path (or use else if):

delete_tree_node(int delete_val, node **root)
{
  node *temp1;
  temp1 = *root;
  if(delete_val == temp1->freq)
  {    
     temp1 = temp1->left;    
     free(*root);    
     *root = temp1;     
  }   
  else if(delete_val < temp1->freq)    
  { 
     delete_tree_node(delete_val, &temp1->left);    
  }
  else if(delete_val > temp1->freq)    
  {
     delete_tree_node(delete_val, &temp1->right);
  }    
}