c - Inserting a string into a Binary Search Tree C

Question

I need to insert strings into a binary search tree but each run through my insert function updates all the nodes and not just the appropriate one. Its required that each word placed in the binary search tree has the exact amount of memory allocated for it (+1 for the NULL pointer).

Here's the struct being used:

typedef struct node_t{
   char *word;
   struct node_t *left, *right;
} node_t;

Here's how I am passing in the word:

for(i=0; i< original_words -1; i++)
{
    fscanf(ifp, "%s", y);
    head = insert(head, y);
}

And here's my insert function:

node_t *insert(struct node_t *head, char *word)
{

if(strcmp(head->word, word) > 0)
{

    if(head->left == NULL)
    {
        head->left = create_node(word);
    }
    else
    {
        head->left = insert(head->left, word);
    }
}

else
{
    if(head->right == NULL)
    {
        head->right = create_node(word);
    }
    else
    {
        head->right = insert(head->right, word);
    }
}

return head;

}

EDIT: Heres an example of the input file.

4
-------
bravo
-------
alpha
-------
gamma
-------
delta

Answer 1

Your answer (the insert function) assumes that head has already been defined on first call, it should start with the line:

if (head == null) return create_node(word);

This will also save you from the need for the null lines in the code. I'm not sure that this is the issue, but it is one.

Perhaps more important: how does create_node set up word? If it's something like:

 new_node->word = word

Then all you are doing is creating a collection of pointers to the word pulled out of the file. It is quite possible that each reading of a word from the file reads the word into the same piece of memory, so all you are doing is collecting a tree of pointers to the same place in memory. It should be something like:

 new_node->word = malloc(strlen(word)+1);
 if (new_note->word == null) {FAIL MEMORY LOSS}
 strcpy(new_node->word, word);