Why does my Recursion using Pointer in C crash?

Question

I'm currently studying Computer Science and we started working with Pointers. I had the feeling that I started to understand pointers but I ran into a problem and can't figure out what went wrong.

We defined a Tree like this:

typedef struct node *tree;
struct node {int key; tree left, right;};

Now we should write a function that creates nodes with three parameters, the key of the node, the left node and the right node that should be "below" the node. I did it like this and it seemed to work:

tree createNode(int n, tree l, tree r){
    tree node = (tree) malloc(sizeof(tree));
    node->key = n;
    node->left = l;
    node->right = r;
    return node;
}

Finally we should write a function that multiplies all leaves of the Tree and i thought the easiest way would be to start at the root and search for the leaves through a recursion and then multiply them. But when i call the function the program seem to crash in the middle of the function. My function looks like this:

int leafprod(tree t){
    printf("%d\n", t->key);

    if (t->left == NULL){
        if (t->right == NULL){
            printf("$1\n\n");
            return t->key;
        }
        printf("$2\n\n");
        return leafprod(t->right);
    }
    if (t->right == NULL){
        printf("$3\n\n");
        return leafprod(t->left);
    }
    printf("$4\n\n");
    return leafprod(t->left) * leafprod(t->right);
}

and i call the function in the main function like this:

int main(){
    tree a = createNode(1, NULL, NULL);
    tree b = createNode(2, NULL, NULL);
    tree c = createNode(3, a, NULL);
    tree d = createNode(4, b, c);

    int n = leafprod(d);

    printf("end: %d", n);

    free(a);
    free(b);
    free(c);
    free(d);

    return 0;
}

I used the print statements to follow the programm and try to locate the error, but in most cases it prints nothing. Then sometimes it prints:

And only two times the program went through the whole code. I believe maybe I am using the malloc function wrong but I cannot tell.

At least this line tree node = (tree) malloc(sizeof(tree)); is incorrect. There must be tree node = (tree) malloc(sizeof( *tree)); — Vlad from Moscow, Jan 31 '23 at 17:30
@VladfromMoscow I think you need `sizeof(*l)` or `sizeof(*r)` (as `tree` is s type). — wohlstad, Jan 31 '23 at 17:35
@VladfromMoscow This results to the error "type name is not allowed". — Kaito, Jan 31 '23 at 17:37
Don't hide pointer types with typedefs as you did here: `typedef struct node* tree;` It only causes confusion, at least in your case here it obviously does. — Jabberwocky, Jan 31 '23 at 17:39
As @wohlstad said, you can use `sizeof(*l)` or `sizeof(*r)`, but you could also use `sizeof(*node)` or `sizeof(struct node)`. — Ian Abbott, Jan 31 '23 at 17:39

wohlstad · Accepted Answer · 2023-01-31T17:52:49.080

3

The problem is in this line:

tree node = (tree) malloc(sizeof(tree));

tree is typedef for a pointer to struct node. Therefore sizeof(tree) is just the size of the pointer.

You should one of the following instead:

tree node = malloc(sizeof(*l));

Or:

tree node = malloc(sizeof(*r));

*l and *r are of type struct node (not a pointer) and this is the element you are trying to create.

Another option as @IanAbbott commented is:

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

Note that node here is the name of the variable, not the type (which in C requires to be prefixes with struct, i.e. struct node). The advantage of this approach is that the statement is not dependent on other variables.

Side notes:

You shouldn't cast the result of malloc. See here:Do I cast the result of malloc?.
It's not a good practice to hide pointer types with typedefs. You can consider to avoid it (you can use typedef struct node Node if you want to save the need to use the struct keyword everywhere).

edited Jan 31 '23 at 17:52

answered Jan 31 '23 at 17:39

wohlstad

12,661
10
26
39

Hiding pointer types with typedefs is a terrible thing.... – Jabberwocky Jan 31 '23 at 17:40
1

More canonically, you could use `tree node = malloc(sizeof(*node));` rather than referring to other variables. – Ian Abbott Jan 31 '23 at 17:41
@IanAbbott yeah, i like this one more. Thank you guys i really struggeled with this one :D – Kaito Jan 31 '23 at 17:43
@Jabberwocky added a note about the pointer typedef. – wohlstad Jan 31 '23 at 17:44
@IanAbbott initially I thought you were wrong, the name of the struct `node` being identical to the variable confused me. Updated my answer with your idea. – wohlstad Jan 31 '23 at 17:53

score 1 · Answer 2 · answered Jan 31 '23 at 17:49

Don't use the typedef for hiding pointer types.

With typedef struct node *tree; you have no idea what tree is in your code hence the confusion.

Typically here tree node = (tree) malloc(sizeof(tree)) you did it wrong, and the main reason was probably because you didn't know anymore what tree actually was.

...
struct node 
{
  int key;
  struct node* left;
  struct node *right;
};

struct node* createNode(int n, struct node*l, struct node*r) {

  struct node* node = malloc(sizeof(*node));   // don't use the cast, it's useless
   ...
}


int leafprod(struct node* t) {
...

Why does my Recursion using Pointer in C crash?

2 Answers2