Recursive function passes NULL pointer when the argument is not NULL

1
votes

The folowing program is intended to store words alphabetically in the Binary Search Tree using the strcmp function. The issue, detailed under the program, is that no pointer is passed in the recursive call of the function in the last part of the function.

typedef struct NodT{
   char word[30];
   struct NodT *left, *right;
} NOD;

void reset_field(NOD *nod){
    int i;
    for(i=0; i<30; i++){
        nod->word[i]='\0';
    }
}

void enter_recursively(NOD *nod, char *word){
    if(nod==NULL){
        nod= (NOD *) malloc(sizeof(NOD));
       nod->left=NULL;
       nod->right=NULL;
       reset_field(nod);
       strcpy(nod->word, word);
       return;
   }

   if(nod->word[0]=='\0'){
       strcpy(nod->word, word);
       return;
   }

   if(strcmp(nod->word, word)==0) return;

   if(strcmp(nod->word, word)<0){
       enter_recursively(nod->right, word);//the problem seems to be here
       printf("right\n");
   }
   else{
       enter_recursively(nod->left, word);//...and here
       printf("left\n");
   }
   //the NULL pointer is being sent over, which is peculiar
}

The thing is that, when I pass the pointers(left, right) from the structure to the recursive function in the if-else conditions, it takes a NULL value on the other side, which it shouldn't do because they are not NULL after alocating the first word in the root and the second in the right or left depending on strcmp, alocation when malloc is used to create the new storage space for the word.

UPDATE: The new script using double pointers:

typedef struct NodT{
    int key;
    char word[30];
    struct NodT *left, *right;
} NOD;

void enter_recursively(NOD **nod, char *word){
        printf("N: %p\n", nod);
    printf("NL: %p\n", (**nod).left);
    printf("NR: %p\n", (**nod).right);
        if(nod==NULL){
            nod=malloc(sizeof(NOD));        
            (**nod).left=NULL;
            (**nod).right=NULL;
            strcpy((**nod).word, word);
            return;
        }
        if((**nod).word[0]=='\0'){
            strcpy((**nod).word, word);
            return;
        }

    if(strcmp((**nod).word, word)==0) return;

        if(strcmp((**nod).word, word)<0){
            enter_recursively((**nod).right, word);
        }
        else{
            enter_recursively((**nod).left, word);
        }

I get segmentation fault and I don't know why.

2
cpointersrecursionreferencebinary-tree
Put the check nod == NULL (or just nod :) before you ever try to access its contents. You are probably just dumping your stack with these accesses. – Jens Gustedt
Please enable warnings on your compiler, you're using return; in a non-void function which makes no sense. Also your fist NULL check will never match, you'll segfault before that if nod is null at function entry. – Mat
oh sorry, I've reedited. Made the return; to make sense now – andreihondrari
This is not directly related to your issue, but for (i = 0; i < 30; i++) { nod->word[0] = '\0'; } makes no sense. – pmg
@pmg, that is just a function I use to clear all the string for writing to file. I've added it in case some of you find it affecting the other functions. Oh...my bad I didn't gave attention to that function until now. It should be word[i] there. – andreihondrari

2 Answers

3
votes

The problem is that *nod is modified but not returned: Change 

void enter_recursively(NOD *nod, char *word)

by 

void enter_recursively(NOD **nod, char *word)

in order to return legal pointer. Inside the function, use *nod instead nod, this is the correct way.

When you pass only NOD * to the function, the allocated memory is not stored properly. Is like when you want to modify a int value inside a function, you pass its address, instead the value.

Besides, verify always null pointers before use them. You can obtain a core.

The final code seams like:

void enter_recursively(NOD **nod, char *word){
    if (*nod==NULL){
        *nod=malloc(sizeof(NOD));        
        (*nod)->left=NULL;
        (*nod)->right=NULL;
        strcpy((*nod)->word, word);
        return;
    }
    if((*nod)->word[0]=='\0'){
        strcpy((*nod)->word, word);
        return;
    }

    if(strcmp((*nod)->word, word)==0) return;

    if(strcmp((*nod)->word, word)<0){
        enter_recursively(&(*nod)->right, word);
    }
    else{
        enter_recursively(&(*nod)->left, word);
    }
0
votes

Your enter_recursively() function allocates a node, maybe even assigns to it, but has no way to pass it back to the caller. Find a way to return something useful to the caller.

UPDATE: for completeness: this is the other way of communicating information from the child back to to its parent: (via the return value)

NOD * enter_recursively(NOD *ptr, char *word){
    int rc;

    if (ptr==NULL){
       ptr = malloc(sizeof *ptr);
       ptr->left = NULL;
       ptr->right = NULL;
       strcpy(ptr->word, word);
       return ptr;
   }

   rc = strcmp(ptr->word, word);
   if (rc==0) return ptr;

   if (rc < 0){
       ptr->right = enter_recursively(ptr->right, word);
       fprintf(stderr, "right\n");
   }
   else {
       ptr->left = enter_recursively(ptr->left, word);
       fprintf(stderr, "left\n");
   }
   return ptr; /* not reached */
}