CODEWITHSUNDEEP
cmallocbinary-search-treedynamic-memory-allocation
Shashank Kumar Pandey
Shashank Kumar Pandey

Reputation: 65

Binary search tree insertion program is showing segmentation fault

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;
}

Upvotes: 1

Views: 111

Answers (2)

AugustinLopez
AugustinLopez

Reputation: 388

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;
}

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 311156

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 )

Upvotes: 2

Related Questions