coping data to a node value in c gives segmentation fault but malloc removes it

Question

I have the below program for inserting node in bst

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


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

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

int main( int argc, const char *argv[]){
    struct node *root= malloc(sizeof(struct node ));

    int x;

    if(root==NULL){
        printf("mem error"); 
        return;
    }
    root=NULL;


    while(1){
        fprintf(stdout, "Enter the value of data\n" );
        fscanf(stdin,"%d",&x);
        root=insert(root,x);

    }


}

struct node * insert(struct node * root, int data ){

    if(root==NULL){
       struct node *root= malloc(sizeof(struct node ));
       root->key = data;
       printf("hiii\n");
       root->left = NULL;
       root->right = NULL;
       return root;
    }else{
       if(root->key >= data){
          root->left = insert(root->left,data);
       }else if(root->key <= data){
          root->right = insert(root->right,data);
       }
       return root;
    }
}

it runs fine.. but if I comment the malloc line in insert function..it gives me a segmentation fault after taking the first value. what is going on here??

Answer 1

You can't comment malloc-line in insert function. The use of malloc() is for allocate new memory dynamically for new nodes to insert in linked-list.

Read: void* malloc (size_t size);

Allocate memory block
Allocates a block of size bytes of memory, returning a pointer to the beginning of the block.

So suppose if you comment/remove malloc line in insert() (read comment):

//struct node *root= malloc(sizeof(struct node ));
root->key = data;  // here illegal operation

root->left = NULL;  //   here illegal operation
root->right = NULL;  //  here illegal operation

then root value will be garbage and you are access and perform read/write action on garbage address not allocated by the process - an memory illegal operation.

Your code will compile because syntax-wise the code is correct but at runtime the OS will detect illegal memory access and can terminate your code. (interesting to note: as OS detects memory right violation by a process -- An invalid access to valid memory gives: SIGSEGV And access to an invalid address gives: SIGBUS). --Actually this cause Undefined behavior. In the worst case your program may seem execute without any failure, producing garbage results.

it gives me a segmentation fault after taking the first value. what is going on here?

As I explained above removing malloc() makes your program behaving in Undefined manner(read: Undefined behaviour). If program runs as Undefined behavior you can's guess what can be happen, in worst case your program may execute without any failure, or may be run partial (that is what you are observing). Thing is that when OS detects illegal memory access and send a signal to terminate the process. (may be first five random-garbage value to root points to a memory associated with our program and according to OS access to that memory is not a illegal operator - while for fifth time random value of root is a memory that doesn't belong to the process and read/write operation on that memory detected by OS hence your code finally terminate with segmentation fault).

Answer 2

malloc gets some memory and returns its address. If you don't store that address in the variable, the variable has NULL (0) in it. When you store to that address (using the pointer), its not a legal memory location and the processor complains with that error.

Answer 3

If you comment out line that allocates memory for root, you're left with

if(root==NULL) {
    //struct node *root= malloc(sizeof(struct node ));
    root->key = data;

which dereferences a NULL pointer. This results in undefined behaviour. Anything can happen at this point. A crash would be most useful and is very likely but isn't guaranteed. If your question is saying that you manage to write to root->key, this is possible but don't count on it working on different builds or different hosts (or even with different runs of the same program on the same computer).

Answer 4

You seem to like throwing memory out of the window ! In main:

struct node *root= malloc(sizeof(struct node ));  // reserve some memory
if(root==NULL)                                    // make sure that memory is reserved
{
    printf("mem error");
    return;
}
root=NULL;                                        // loose the address of the memory

This should just be:

struct node *root = NULL;

Answer 5

When root to NULL, addressing root->key put you in a very problematic part of memory. Your program managed to survive one iteration before crashing.