Comparing int to NULL in C - is this tutorial incorrect?

Question

I'm looking at this tutorial http://www.learn-c.org/en/Binary_trees and in the insert function it compares an int to NULL. It seems to run fine on the tut site but it didn't work for me and my research tells me it should not work. My code is below.

1. Am I wrong here or is the tutorial wrong?

2. If the tutorial is wrong is there any way to dynamically set the value for the first node of the BST? I thought about checking if left and right were both null but that would just keep resetting the first node. Having a third pointer for the value of the node seems wasteful but maybe it's the only way?

   #include <stdio.h>
   #include <malloc.h>
   struct bstNode {
       int val;
       struct bstNode *left;
       struct bstNode *right;
   };
   
   int insert(struct bstNode *head, int val);
   
   void printDFS(struct bstNode *head);
   
   int main() {
       struct bstNode *bstTree = malloc(sizeof(struct bstNode));
       insert(bstTree, 8);
       insert(bstTree, 5);
       insert(bstTree, 98);
       insert(bstTree, 2);
       insert(bstTree, 15);
       insert(bstTree, 65);
       insert(bstTree, 15);
       printDFS(bstTree);
   }
   
   int insert(struct bstNode *head, int val) {
       //This is the problem statement, it contains random data when I debug as it's uninitialized
       if (head->val == NULL) {
           head->val = val;
           return 0;
       }
   
       if (val < head->val) {
           if (head->left != NULL) {
               return insert(head->left, val);
           } else {
               head->left = malloc(sizeof(struct bstNode));
               head->left->val = val;
               return 0;
           }
       } else {
           if (head->right != NULL) {
               return insert(head->right, val);
           } else {
               head->right = malloc(sizeof(struct bstNode));
               head->right->val = val;
               return 0;
           }
       }
   }
   
   void printDFS(struct bstNode *head) {
       if (head->left != NULL) printDFS(head->left);
       printf("%d ", head->val);
       if (head->right != NULL) printDFS(head->right);
   }
   

Answer 1

The tutorial is incorrect. It makes two invalid assumptions.

1. It assumes that NULL is equivalent to 0. While in most cases it is defined at (void *)0, it won't always necessarily be the case. It's also using a pointer where an int is expected, so there's a dependency on the representation of a pointer.
2. It assumes the initial node has 0 in val. When memory is allocated with malloc, the memory is not initialized (as you've found out).

This code also functions by assuming that 0 is not a valid value to be inserted into the list, since it uses 0 for a sentinel value to denote an empty list.

Working with the assumption that 0 is used as a sentinel, the code can be fixed as follows.

First, when creating the initial node, use calloc instead of malloc. The calloc function will initialize all bytes to 0. This will give you an initial member with val set to 0 and both left and right set to NULL.

Also, you should always check the return value of malloc, calloc, and realloc in case they fail.

int main() {
    struct bstNode *bstTree = calloc(1, sizeof(struct bstNode));
    if (bstTree == NULL) {
        perror("calloc failed");
        exit(1);
    }

Second, get rid of the integer/pointer comparison by replacing NULL with 0.

    if (head->val == 0) {

Doing those 2 things should get the code to work properly.

Taking a step back and looking at the bigger picture, there are some design issues here.

The insert function returns an int, but the return value is never used. In fact, this function can only ever return 0. Better to change the return type to void.

Having an empty tree contain a single node with a sentinel value restricts the values you can put in. Better to have an empty tree by having the head node being a NULL pointer. This can be addressed in the insertion function by passing in the address of the head pointer so it can be modified if the list is empty:

void insert(struct bstNode **head, int val) {
    if (*head == NULL) {
        *head = malloc(sizeof(struct bstNode));
        if (*head == NULL) {
            perror("malloc failed");
            exit(1);
        }
        (*head)->val = val;
        (*head)->left = NULL;
        (*head)->right = NULL;
        return;
    }

    if (val < (*head)->val) {
    ...

Then you call it like this:

struct bstNode *bstTree = NULL;
insert(&bstTree, 8);
...

Answer 2

if (head->val == NULL) {
    head->val = val;
    return 0;
}

I think the tuto want check if val is NULL because insert return a int. You should replace insert function by something like that:

struct bstNode *new_bstNode(int val, struct bstNode *left, struct bstNode *right)
{
    struct bstNode *elem = malloc(sizeof(*elem));
    if (elem == NULL)
        return NULL;
    elem->val = val;
    elem->left = left;
    elem->right = right;
    return elem;
}

struct bstNode *insert(struct bstNode *head, int val) {
    if (head == NULL)
        return new_bstNode(val, NULL, NULL);

    if (val < head->val) {
        if (head->left != NULL)
            return insert(head->left, val);
        else
            return head->left = new_bstNode(val, NULL, NULL);
    } else {
        if (head->right != NULL)
            return insert(head->right, val);
        else
            return head->right = new_bstNode(val, NULL, NULL);
    }
}

So your main need to be replace by

int main() {
    struct bstNode *bstTree = insert(bstTree, 8);
    insert(bstTree, 5);
    insert(bstTree, 98);
    insert(bstTree, 2);
    insert(bstTree, 15);
    insert(bstTree, 65);
    insert(bstTree, 15);
    printDFS(bstTree);
}