Tree doesn't grow beyond size 3

Question

I am trying to implement the insertion subroutine in a binary search tree, each of whose nodes has a word(string) as key. I'm taking the words from STDIN and inserting them using the insert function. But whenever I take a inorder traversal, I find out that the tree is not growing beyond 3 nodes. What can be wrong? My code is attached here:

typedef struct treenode
{
  char word[20];             //word is the key for each node
  struct treenode *left;
  struct treenode *right;

} treenode;



treenode *insert (treenode *node, char *word)   
{   
  if(node==NULL)                       //if a null node is reached,make a temp node and append it
  {
    treenode *temp;
    temp = (treenode *) malloc(sizeof(treenode));
    strcpy (temp ->word,word);
    temp-> left = NULL;
    temp-> right = NULL;
    return temp;
   }


    if ((strcmp(word, node ->word)>0))  //if the key is greater than node.word,go to right child
    {
        node-> right = insert(node-> right, word);
    }
    else if(strcmp(word,node->word)<=0)  //if key <node.word,go to left child
    {
        node-> left = insert(node-> left, word); 
    }

}

void printinorder(treenode *node)
{

   if(node == NULL) return;
   printinorder(node-> left);
   printf("%s ",node-> word);
   printinorder(node-> right);

}



int main()
{
    treenode *root = NULL;
    char string[20];
    scanf("%s",string);  //first input is taken once here and once again inside loop,but its OK
    root = insert(root, string+1);  //duplicate entries are also stored

    while(strcmp(string,".")!=0)   //input is terminated by a full stop
    {
        insert(root, string+1); 
        scanf("%s",string);
    }


    printinorder(root);           //finally printing the BST
    return 0;
}

You may want a return somewhere toward the bottom of this thing. And [avoid casting malloc in C programs](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — WhozCraig, Oct 11 '14 at 05:48

David C. Rankin · Answer 1 · 2014-10-11T07:34:21.877

The problem with your implementation is that you are trying to combine the create_node and insert into a single function which and then use that single function as a one-size-fits-all solution for tree initialization and insertion. Here it was causing complications with the return type from insert (as noted in the comments) and likely caused you to miss a needed recursion in insert. (note the addition of and an else in insert under both the tree->right and tree->left code)

You are better served splitting the create_node and insert routines into separate functions. This allows create_node to be defined as type treenode and insert to be defined as type void. This simplifies the code for each and makes following the logic easier and more readable. Doing so, your code then becomes:

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

typedef struct treenode
{
char word[20];             //word is the key for each node
struct treenode *left;
struct treenode *right;

} treenode;

treenode* create_node (char *word)
{
    treenode* tmp = malloc (sizeof (struct treenode));
    if (tmp) {
        strcpy (tmp ->word,word);
        tmp->left = NULL;
        tmp->right = NULL;
    } else {
        fprintf (stderr, "%s() error: memory exhausted\n", __func__);
    }
    return tmp;
}

void insert (treenode *tree, char *word)
{

    if (strcmp (word, tree->word) > 0)
    {
        if (tree->right == NULL) {
            tree->right = create_node (word);
            insert (tree->right, word);
        } else {
            insert (tree->right, word);
        }
    }
    else if (strcmp (word, tree->word) < 0)
    {
        if (tree->left == NULL) {
            tree->left = create_node (word);
            insert (tree->left, word);
        } else {
            insert (tree->left, word);
        }
    }
}

void printinorder(treenode *node)
{
    if(node == NULL) return;
    printinorder(node-> left);
    printf("%s ",node-> word);
    printinorder(node-> right);
}

int main()
{
    treenode *root = NULL;
    char string[20];
    scanf ("%s",string);  //first input is taken once here and once again inside loop,but its OK
    root = create_node (string);  //duplicate entries are also stored

    while (strcmp (string,".")!=0)   //input is terminated by a full stop
    {
        insert (root, string); 
        scanf ("%s",string);
    }

    printinorder(root);           //finally printing the BST

    return 0;
}

build/run:

$ gcc -Wall -Wextra -o bst bst.c
$ ./bst
my_dog
has
fleas
my_cat
likes
snakes
.
fleas has likes my_cat my_dog snakes

Also, as mentioned in the comments - do not cast malloc. It is unnecessary and increases the likelihood of error.

Tree doesn't grow beyond size 3

1 Answers1