Typedefs, tagged and untagged structures, and incompatible pointer types

Question

Consider the following C code snippet:

typedef struct node{
    int val;
    struct node* left;
    struct node* right;
}node;

void inorderTraversal(node *p){
    inorderTraversal(p->left);
    printf("%d",p->val);
    inorderTraversal(p->right);
}

If I write only typedef struct instead of typedef struct node, I get a warning saying "passing argument of incompatible pointer type" when I call inorderTraversal(root) in main(). Why do I get this warning even though the program doesn't show any error?

Solution

If you don't give a tag name to the struct,

struct node* left;

in the struct definition declares a new (incomplete) type struct node. So when you pass a pointer to that (incomplete) type, where a node* is expected, you're passing a pointer of an incompatible type.

When the struct you define has members that are pointers to the same type, you must be able to name that type in the definition, so the type must be in scope.

If you give the struct a name, the type is - from that point on - in scope and can be referred to, although not yet complete, as struct node (if the tag is node). After the typedef is complete, the type can then be referred to as either struct node or node, whichever you prefer.

But if you don't give the struct a tag, the type is anonymous until the typedef is complete, and cannot in any way be referred to before that. And since when the line

struct node *left;

is encountered, no type that struct node refers to is known, that line declares a new type, struct node, of which nothing is known. The compiler has no reason to connect that type with the one currently being defined. So at that point, the struct contains a member that is a pointer to an unknown incomplete type. Now, in inorderTraversal, when you call

inorderTraversal(p->left);

with node *p, by the definition of node, p->left is a pointer to the unknown incomplete type struct node. If p has been created so that p->left is actually a pointer to node, things will work nevertheless (except possibly on platforms where pointers to different types have different representations), but you're passing a pointer to one type where a pointer to a different type is expected. Since the one type is incomplete, it is incompatible with the expected type.