Problem with incompatible pointers in BST using c language

Question

I am working on a BST

    
    typedef struct Node
    {
        double key;
        struct Node* left;
        struct Node* right;
    } Node;

    Node *newNode(double key)
    {
        Node *node = (Node*) malloc(sizeof(Node));
        node->left = NULL;
        node->right = NULL;
        node->key = key;
    
        return node;
    }

    Node *insertNode(Node *root, Node *new_Node)
    {
    
        if(root == NULL) {
            return new_Node;
        }

        if(root->key == new_Node->key) {
            printf("Duplicate node %d\n", root->key);
            return root;
        }

        if(root->key < new_Node->key) {
            root->right = insertNode(root->right, new_Node);
        } 
        else {
            root->left = insertNode(root->left, new_Node);
        }

        return root;

    }

I'm getting the following error

    warning: passing argument 1 of 'insertNode' from incompatible pointer type [-Wincompatible-pointer-types]
         root->right = insertNode(root->right, new_Node);

Don't know what I'm doing wrong. Please help!

Answer 1

You probably don't initialize the root node correctly:

int main() {
    Node *root = NULL;
    insertNode(root, newNode(42));
    // ...
}

In main() the root variable remains NULL as arguments are passed by value in C. It will also will also leak newNode(42). Instead you need to do:

int main() {
    Node *root = insertNode(NULL, newNode(42));
    insertNode(root, newNode(41));
    // ...
}

If you ever want to replace the root node, then you need to change the interface to pass in a Node **root instead (hint: you do when you want a balanced tree).

Prefer passing the variable rather than the type to sizeof, don't cast the void * and check that malloc() was successful, i.e.:

Node *node = malloc(sizeof *node);
if(!node)
   return NULL; // let caller deal with it