Binary search tree in C. Program not working.

Question

I tried to implement Binary search tree through C proggramming. I wrote only two functions. The program compiles perfectly. But when it is being run, it works upto the point of asking user to "Enter the data to be inserted". After the data is inserted the program is being stopped.

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

typedef struct Node
{
    int info;
    struct Node *left;
    struct Node *right;
}node;


node* insert(node *root, int data);
void inorder(node* root);


int main()
{
    int data,choice;
    node *root;
    printf("----------------MENU---------------\n");
    printf("1. Insert\n");
    printf("2.Inorder traversal\n");
    printf("3.Exit\n");
    while(1)
    {
        printf("Enter your choice: ");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1: 
            printf("Enter the data to be inserted: ");
            scanf("%d",&data);
            root=insert(root,data);
            break;
            case 2:inorder(root);
            break;
            case 3:
                exit(0);
        }
    }
    return 0;
}

node* insert(node *root, int data)
{
    if(root==NULL)
    {
        root=(node *)malloc(sizeof(node));
        root->info=data;
        root->left=root->right=NULL;
        return root;
    }
    else if(data<=root->info)
    {
        root->left=insert(root->left,data);
        return root;
    }
    else if(data>=root->info)
    {
        root->right=insert(root->right,data);
        return root;
    }
}

void inorder(node* root)
{
    if(root==NULL)
    return;

    else
    {
    inorder(root->left);
    printf("%d",root->info);
    inorder(root->right);

    }

}

Answer 1

Diagnosis

You don't initialize root (so it is not reliably NULL); you pass it to insert(); insert() uses it and things go haywire.

node *root = 0;   // Or NULL

With this change, the code runs. The printing doesn't leave spaces between the numbers, which is a bit ugly, but the functionality seems to be OK. You'll need to write code to free the allocated tree before long.

---

Commentary

I observe that when I compile your code with the default options I use (on a Mac running macOS Sierra 10.12.3 using GCC 6.3.0), I get warned about this. I saved your code into ub37.c:

$ gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes \
>     -Wstrict-prototypes -Wold-style-definition -c ub37.c
ub37.c:16:5: error: function declaration isn’t a prototype [-Werror=strict-prototypes]
 int main()
     ^~~~
ub37.c: In function ‘main’:
ub37.c:16:5: error: old-style function definition [-Werror=old-style-definition]
ub37.c: In function ‘insert’:
ub37.c:63:1: error: control reaches end of non-void function [-Werror=return-type]
 }
 ^
ub37.c: In function ‘main’:
ub37.c:33:17: error: ‘root’ may be used uninitialized in this function [-Werror=maybe-uninitialized]
             root=insert(root,data);
             ~~~~^~~~~~~~~~~~~~~~~~
cc1: all warnings being treated as errors
$

The 'strict prototype' and 'old style definition' warnings are resolved by writing int main(void). This is not the end of the world as an issue, but it is easily fixed.

The 'control reaches end of non-void function' could be resolved by replacing the final else if with just else in insert(). I observe that the equality part of >= was covered by the previous else if (data <= root->info) test, too. At one level, this is not critical — you've covered all the cases. At another level, it is easily fixed and the fixed code does what you want so it should be fixed.

The main bug is identified by the 'root may be used uninitialized' error.

Because I compile with -Werror too, any one of those warnings would prevent the code compiling.

Make sure you're compiling with similarly stringent warning options. It makes your code better.