1

The node insertion code is throwing segmentation fault. This code is throwing segmentation fault when i am trying to print the data stored in the root node.

Below is the implementation of the insertion program for the Binary Search Tree. This program is using recursion to insert a given node.

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

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

struct node *make (int);
struct node *insert (struct node *, int);

void
main ()
{
  struct node *root;
  root = NULL;

  insert (root, 2);
  insert (root, 3);
  insert (root, 4);
  insert (root, 5);
  insert (root, 6);
  insert (root, 7);
  printf ("%d", root->data);
}

struct node *
make (int x)
{
  struct node *temp;
  temp = (struct node *) malloc (sizeof (struct node *));
  temp->data = x;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}

struct node *
insert (struct node *root, int x)
{
  if (root == NULL)
  {
    root = make (x);
  }
  else
  {
    if (x <= root->data)
    {
      root->left = insert (root->left, x);
    }
    else if (x > root->data)
    {
      root->right = insert (root->right, x);
    }
  }
  return root;
}
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
Shashank Kumar Pandey
  • 65
  • 5

2 Answers2

2

The problem is that you are not assigning the returned value of the function insert to the node root.

Write

root = insert(root,2);

//...

Another problem is that you are allocating memory incorrectly

temp = (struct node *) malloc (sizeof (struct node *));
                                       ^^^^^^^^^^^^^

There must be

temp = (struct node *) malloc (sizeof (struct node ));
                                       ^^^^^^^^^^^^^

Also within the function insert the inner if statement should look like

if (x < root->data)
{
    root->left = insert (root->left, x);
}
else
{
    root->right = insert (root->right, x);
}

Pay attention to that according to the C Standard the function main without parameters shall be declared like

int main( void )
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • Is `malloc()` return type casting useless as stated at: https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc – EsmaeelE Oct 02 '19 at 10:04
  • @EsmaeelE Sometimes it is useless, sometimes it makes the code self-documented and allows to avoid an error. – Vlad from Moscow Oct 02 '19 at 10:05
  • can you please explain true way of using `malloc()` especially the situation we must not cast its return values and when cast is good. – EsmaeelE Oct 02 '19 at 10:09
  • @EsmaeelE For example can you say whether this code is valid p = malloc( sizeof( int[M][N] ) );? Or what can you say about the type of the allocated memory in this statement p = malloc( sizeof( *p ) )? Between this statement and the declaration of p there can be dozens of screens. Are you going to scroll the source code forward and backward to know what is the declaration of p? – Vlad from Moscow Oct 02 '19 at 10:15
  • I find out in two case explicit type conversion on return type of malloc, ie: `p =(cast to type of p) malloc( sizeof( *p ) )` helps to make code clear and from this point we know p is pointing to which type of memory instead of search for p declaration in other places. – EsmaeelE Oct 02 '19 at 10:31
  • @EsmaeelE Moreover in C++ there is not allowed to assign a pointer of the type void * to a pointer of some other type. Using casting you help the compiler to find a bug for you at compile-time. – Vlad from Moscow Oct 02 '19 at 10:43
0

Do not ignore the return value of insert:

void main(){
  struct node* root;
  root = NULL;

  root = insert(root,2);
  insert(root,3);
  insert(root,4);
  insert(root,5);
  insert(root,6);
  insert(root,7);

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

Other points you might want to consider:

  • I cannot recommend using void main(): mostly because this is non-standard. Use int main(void) and return 0.
  • Use printf("%p", root); for verification : if the value is 0x0, your pointer is NULL.
  • When performing a memory allocation in a sub-function, you should always check if the allocation has succeeded.
struct node *
make (int x)
{
  struct node *temp;
  if ((temp = (struct node *) malloc (sizeof (struct node))) == NULL)
      return (NULL);
  temp->data = x;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}
AugustinLopez
  • 348
  • 1
  • 3
  • 13
  • 1
    On any other path, `insert` just returns the original root unchanged. So, it's always fine to reassign the callers `root` variable to the return value. – Useless Oct 02 '19 at 09:51
  • If `insert` return NULL in case of failure, as it probably should, you will lose the `root` pointer. – AugustinLopez Oct 02 '19 at 09:55
  • 1
    True! But the way it is written now suggests it intends the caller to save the return value, and the caller doesn't do that. And the current code is going to SEGV on allocation failure anyway - it needs a redesign to survive that. – Useless Oct 02 '19 at 10:25
  • Also true ! My solution is definitely not perfect: while I wanted to answer the OP's question and specific problem with the least amount of code modification, I did not address all memory handling issues. – AugustinLopez Oct 02 '19 at 11:41
  • 1
    _When performing a memory allocation in a sub-function, you should always check if the allocation has succeeded._ and if you're running on a *nix OS, you should also try to allocate to it too, as the actual memory allocation is deferred and `malloc()` always returns `True` (such fun) https://stackoverflow.com/q/48585079/4022608 may be useful – Baldrickk Oct 02 '19 at 14:15