Crash when trying to print the value at the root of a binary tree

Question

Simple enough program so far: a binary tree made up of nodes containing an integer value, and a pointer to the left and right branch of the node.

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

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

void insert(Node *root, int val);

int main(void){
    Node *root = NULL;

    insert(root, 5);
    insert(root, 3);

    printf("%d\n", root->val);


    return 0;
}

void insert(Node *root, int val){
    if(root == NULL){ // Create tree if root is empty
        root = malloc(sizeof(struct node));
        root->val = val;
        root->left = NULL;
        root->right = NULL;
    } else if(val < root->val){ // branch to left of tree if new value is less than root value
        if(root->left == NULL){
            root->left = malloc(sizeof(struct node));
        }

        root->left->val = val;
    } else if(val > root->val){ // branch to right of tree if new value is greater than root value
        if(root->right == NULL){
            root->right = malloc(sizeof(struct node));
        }

        root->right->val = val;
    }
}

For whatever reason, the insertion goes fine. I can input both 5 and 3 (arbitrary) fine. But I can't print out the value '5' that should be in root->val? The program just completely crashes. Have I overlooked something?

Try printing the pointer value of `root` after the first `insert()` - it isn't what you think.... — John3136, Apr 18 '17 at 01:10
One way you goofed was not doing research. About half of all linked-list/tree posts on SO have this 'only updates local vars' problem. — ThingyWotsit, Apr 18 '17 at 07:05

score 1 · Accepted Answer · answered Apr 18 '17 at 01:22

The problem is in the signature of insert:

void insert(Node *root, int val);

It cannot possibly take NULL for the root parameter, because it has no way to communicate back the change that happens to it inside the function. Any modifications to root inside insert remain local to insert, because pointers are passed by value, i.e. copied.

You have two general choices for a good signature:

Make insert return the new root, i.e. Node *c If you use this approach, the callers will need to make calls as follows: root = insert(root, 5); or
Pass Node** instead of Node*, i.e. void insert(Node **root, int val); If you use this approach, the callers will need to make calls as follows: insert(&root, 5). Of course the implementation of insert will need to change as well, because an extra level of indirection requires an additional dereference.

I think you need to brush up on [pass by value](http://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value); *scope and memory* seem orthogonal. — autistic, Apr 18 '17 at 03:38

Crash when trying to print the value at the root of a binary tree

1 Answers1