Binary Search Tree program in C behaving oddly

Question

I wrote the following code for creation of Binary Search Tree, but when the creation function is called and it tries to call the insertNode(...) for the 1st time the program hangs up. Following is the code :

struct BstNode{
    int value;
    struct BstNode* left;
    struct BstNode* right;
};

struct BstNode *root; 

struct BstNode* insertNode(struct BstNode* root, int data){
    if(data <= root->value)
        root->left = insertNode(root->left, data);
    else
        root->right = insertNode(root->right, data);

    printf("%d  ",root->value);
    return root;
}


void create(struct BstNode* root){ 
    int data;
    if(root == NULL){
        //create the root node
        printf("\nInside create");
        root = (struct BstNode*) malloc(sizeof(struct BstNode));
        printf("\nData :: ");
        scanf("%d",&data);
        root->value = data;
        root->left = NULL;
        root->right = NULL;
    }
    else{
        printf("\nCalling insertNode()");
        printf("\nData :: ");
        scanf("%d",&data);
        root = insertNode(root, data);  // The program hangs up here : the very first time this line is executed
        printf("\nCalled insert");
    }
}

int main(){
    root = NULL;
    int i;
    for(i=0;i<5;i++){
        create(root);
        printf("%d ",root->value); // For checking the value 
    }
    return 0;
}

Could anybody point out my mistake. Any suggestion(s) is helpful.

Answer 1

The function insertNode has infinite recursion which causes your program to crash.

More specifically

struct BstNode* insertNode(struct BstNode* root, int data){
  if(data <= root->value)
      root->left = insertNode(root->left, data);
  else
      root->right = insertNode(root->right, data);

printf("%d  ",root->value);
return root;

You go in function and check if(data <= root->value). In both cases (true and false) you call insertNode function again which then call for insertNode again and again - you will never got to the return statement. Recursive function need to have base case which returns some value without calling itself again.

thisFunction()
   if (base case)
     return value;
   else
     return thisFunction()

In case of binary search trees, the base case is when you the key(data) you are inserting is A) inserted key is bigger than current node AND current node's right child is leaf (null) or B) inserted key is smaller (or equal depending on how you want to resolve ties) than your current node AND current node's left child is null .(data > cur->data && cur->right == NIL) or (data < cur->data && cur->left == NIL). Should you hit one of these cases just make the new node right child or left child of the current node.

Answer 2

Could anybody point out my mistake.

The main problem is that createNode modifies a local copy of root. The global variable root is never modified, and remains set to NULL.

Any suggestion(s) is helpful.

1. Avoid using global variables. Move root to be a local variable in main.
2. Change the signature and purpose of create so that it simply creates a node, and nothing else.
3. Don't cast the results of malloc. See Specifically, what's dangerous about casting the result of malloc?
4. Use insertNode instead of create in main. Call create from insertNode at the right place.
5. Add a function that prints the contents of the tree.
6. While testing the code, use random numbers instead of user entered data.
7. Allow the flexibility of creating more than 5 nodes by using a command line argument.

Here's my suggestion for the program:

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

struct BstNode{
   int value;
   struct BstNode* left;
   struct BstNode* right;
};

struct BstNode* create(int data){ 
   printf("Creating a node with value: %d\n", data);
   struct BstNode* node = malloc(sizeof(*node));
   node->value = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}

struct BstNode* insertNode(struct BstNode* root, int data){
   if ( root == NULL )
   {
      return create(data);
   }

   if(data <= root->value)
      root->left = insertNode(root->left, data);
   else
      root->right = insertNode(root->right, data);

   return root;
}

void print(struct BstNode* node, int indent, char const* nodeName)
{
   if ( node == NULL )
   {
      return;
   }

   for (int i = 0; i < indent; ++i )
   {
      printf("   ");
   }
   printf("%s: %d\n", nodeName, node->value);
   print(node->left, indent+1, "left");
   print(node->right, indent+1, "right");
}

int main(int argc, char** argv){
   struct BstNode *root = NULL; 
   int i;
   int data;
   int num = 5;
   if ( argc > 1 )
      num = atoi(argv[1]);

   srand(time(NULL));
   for(i=0;i<num;i++){
      data = rand()%10000;
      root = insertNode(root, data);
   }

   printf("\n");
   print(root, 0, "root");
   return 0;
}

Answer 3

The algorithm for inserting in such tree is (insert(node, value)) :

• if node is NULL allocate a node, set left/right to NULL (it is a leaf), set value to value, return the allocated node
• else if value < node->value: node->left = insert(node->left, value)
• else : node->right = insert(node->right, value)
• return node (so that we have homogeneous code)

Inserting from let say your main is the same: root = insert(root, val).

Rather than returning the value you can also pass a pointer to your pointer (&root) but then you'll have to deal with dereferencing it in the function. You don't seems to be very familiar with pointers, you really should read more about that if you plan to play with such structures.

Note also that your printf in your main function is not useful: in that kind of trees the root value will always be the 1st inserted value (or you would have to perform shifts in the tree to equilibrate the branches, but this is an other problem). Printing a btree implies a recursive function too, and you have to choose how to print it (deep-first, sorted…). Example: if node is NULL return; call yourself on left; print value; call yourself on right → will print content sorted in small-to-large order.