What the following line of code with malloc does?

Question

I have the following implementation to mirror the binary tree.

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

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)

{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}


/* Change a tree so that the roles of the  left and
    right pointers are swapped at every node.

 So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/
void mirror(struct node* node)
{
  if (node==NULL)
    return; 
  else
  {
    struct node* temp;

    /* do the subtrees */
    mirror(node->left);
    mirror(node->right);

    /* swap the pointers in this node */
    temp        = node->left;
    node->left  = node->right;
    node->right = temp;
  }
}


/* Helper function to test mirror(). Given a binary
   search tree, print out its data elements in
   increasing sorted order.*/
void inOrder(struct node* node)
{
  if (node == NULL)
    return;

  inOrder(node->left);
  printf("%d ", node->data);

  inOrder(node->right);
} 


/* Driver program to test mirror() */
int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);

  /* Print inorder traversal of the input tree */
  printf("\n Inorder traversal of the constructed tree is \n");
  inOrder(root);

  /* Convert tree to its mirror */
  mirror(root);

  /* Print inorder traversal of the mirror tree */
  printf("\n Inorder traversal of the mirror tree is \n"); 
  inOrder(root);

  getchar();
  return 0; 
}

I am talking about the following line:

  struct node* node = (struct node*)
                       malloc(sizeof(struct node));

I have intermediate knowledge of c/c++ but I am quite afraid of pointers. Even after several tries I have never been able to get pointers. I avoid them as far as possible but when come to implementing data structures like trees there is no other options. Why are we using malloc and sizeof here? Also why are we casting (struct node*)?

Answer 1

First of all casting when using malloc in C is not necessary. (see here)

You are malloc-ing because you are allocating heap memory of the size of a node struct. You see in C you have to keep in mind where all the variables are stored. Namely the stack and heap (see here)

Inside a function your variables are termed local variables, which is stored in the stack. Once you leave the function that variables in the stack are cleared.

To be able to reference or use local variables outside of the function you have to allocate memory in the heap, which is what you are doing here. You are allocating memory in the heap so that you can reuse the same variable in other functions as well.

In summary:

• Variables within a function are local to the function, hence the term local variable
• For other functions to access the local variable, you have to allocate memory in the heap to share that variable with other functions.

To give you an example why, consider the following code:

#include <stdio.h>
#include <string.h>

char *some_string_func()
{
    char some_str[13]; /* 12 chars (for "Hello World!") + 1 null '\0' char */

    strcpy(some_str, "Hello World!");

    return some_str;
}

int main()
{
    printf("%s\n", some_string_func());
    return 0;
}

Its pretty simple, main is simply calling a function some_str_func which returns a local variable some_str, compiling the above code would work, but not without warnings:

test.c: In function ‘some_string_func’:
test.c:11:9: warning: function returns address of local variable [enabled by default]

Although it compiles note that some_str in some_str_func() is returning a local variable to the function (i.e. in the function's stack). Since the stack is cleared once you leave the function some_str_func(), in main() it would not be possible to get the contents of some_str which is "Hello World".

If you attempt to run it you get:

$ gcc test.c
$ ./a.out

$

It prints nothing, cause it cannot access some_str. To remedy it you allocate some memory space for the string "Hello World" instead. like so:

#include <stdio.h>
#include <string.h>

char *some_string_func()
{
    char *some_str;

    /* allocate 12 chars (for "Hello World!") + 1 null '\0' char */
    some_str = calloc(13, sizeof(char));

    strcpy(some_str, "Hello World!");

    return some_str;
}

int main()
{
    char *str = some_string_func();
    printf("%s\n", str);

    free(str);  /* remember to free the allocated memory */
    return 0;
}

Now when you compile and run it, you get:

$ gcc test.c
$ ./a.out
Hello World!
$

If you are having a hard time understanding C, I know many people find "The C Programming Language" by Brian W. Kernighan and Dennis Ritchie a really good reference, however a more modern and graphical (even fun to read! seriously) book is Head First C By David and Dawn Griffiths, they explain many important C concepts such as Heap and Stack, difference between dynamic and static C libraries, why using Makefiles is a good idea, how does Make work, and many more concepts not previously explained in common C books, definitely worth a look.

Another good online resource is Zed Shaws Learn C the Hard way, in which he provides good code examples and notes.