How is this code working without returning the allocated pointer?

Question

I am using this particular code for creating a binary tree and the code itself is working, but I seem to be lacking a critical concept to understand the code.

Node structure

typedef struct node{
  int data;
  struct node *left,*right;
}* Node;

The create function

Node create(){
    Node root = (Node) malloc(sizeof(struct node));
    int x;
    scanf("%d",&x);
    if(x==-1) //create a null node
      return NULL;
    root->data=x;
    root->left = create();
    root->right = create();
}

The call for the function is

Node root=create();

In the create function there is no pointer to the root node being passed.
Within the function, a new node is being created, allocated memory and value of the node is assigned. But nowhere in the code is the pointer to the newly created node being passed or returned.

So how does this code work?

PS: The return type is Node. I think this is relevant but I have no idea as to why it is so. It might as well as be void as no value is returned.

Answer 1

OK, first off, there is a clear and straightforward bug in this function...

Node create(){
    Node root = (Node) malloc(sizeof(struct node));
    int x;
    scanf("%d",&x);
    if(x==-1) //create a null node
      return NULL;
    root->data=x;
    root->left = create();
    root->right = create();
}

which the compiler should have pointed out to you:

test.c: In function ‘create’:
test.c:18:1: warning: control reaches end of non-void function [-Wreturn-type]

(If your compiler ate this code without any complaints at all, turn on warnings. GCC in particular is way too permissive by default; if you're using GCC you should give it the -Wall option essentially always, and probably a bunch more -Wsomething options as well.)

The bug is simply that there's a missing last line:

return root;

Now, your actual question appears to be "I know there's a bug, but why does it work anyway?" and before I get into that, I need you to acknowledge that you understand that, if it works, it only works by accident, on the computer and with the compiler you happen to be using right now. create has what we call "undefined behavior", which means that it's allowed to do anything at all, including appearing to work correctly, but also failing catastrophically.

There is a plausible explanation for why it works anyway: on many CPUs, the register used to return pointers is also a convenient scratch register, so when compiling the statement

root->right = create();

the compiler may place root in the return-value register in order to perform the memory access root->right = .... As there are no operations after that point, the generated machine code "falls off the end", without officially putting a return value in that register, but also not removing the local variable root from that register. And so it appears to work.

---

Incidentally, there are a bunch more bugs in this function:

Node create(){

This has one mostly-harmless semantic error and one style error; it should be written

Node create(void)
{

In C, for historical reasons, you must write (void), not (), to define a function that takes no arguments. This is technically defining a function that takes an unspecified number of arguments, which means the compiler won't complain if you call create with arguments.

In C, unlike in some other languages you may be familiar with, the opening curly brace of a function definition should always be placed on its own line.

    Node root = (Node) malloc(sizeof(struct node));

In C (unlike C++), do not cast the return value of malloc. It is not necessary, and if you don't, the compiler will remind you when you forgot to include stdlib.h and therefore your pointers are being truncated to the width of int.

    int x;
    scanf("%d",&x);

Never use scanf in production code. Also, you are not checking for input errors.

    if(x==-1) //create a null node
      return NULL;

This leaks the just-allocated node when x is equal to -1. This check should occur before the call to malloc.

Also, your indentation is inconsistent: you used 4-space indent for the first level and 2-space indent for the second level. It doesn't matter what indentation style you use, but it does very much matter that you pick a style and stick to it throughout your program.

(And don't use tabs, because programs indented with tabs don't look the same for everybody. 8-space indent is fine, but they should actually be eight spaces.)

Answer 2

The problem here is that you are omitting the return statement at the end of create. C compilers are surprisingly permissive when it comes to this and will often compile just fine (though with warnings. You do have warnings enabled don't you!?).

Most likely the function is returning some arbitrary value sitting around in a register or in some stack frame, which luckily is the address of root so everything works as expected (see Function with missing return value, behavior at runtime).

If you add return root; at the end of the function, it should continue working as before minus the undefined behavior.

Answer 3

There is no use of create() function until it returns pointer which is pointing to dynamically allocated memory.

Answer 4

Congratulations, you found a memory leak. The function is allocating resources on the heap but it doesn't pass control over to you or frees it.