C - Implementation of Binary Tree Causing Strange Behavior on Insert

Question

I have my binary tree setup like this:

`

I also initialize the first node of the BT like so:

`

Everything works fine up to this point. However, when I try to insert into my BT, I keep getting unexpected behavior. My insert function looks like this.

`

However, when I run the code from the main function and try to insert into the BT, the first node shows up just fine, but the second node becomes some big, strange number. When I run it in a debugger, it shows the number I'm expecting, but that is not the number that gets printed out. Here is my main method.

`

The problem is in my insert function, but I'm not sure what is going wrong because when I run it through a debugger, I get the expected value of 5 and 6.

Answer 1

In these statements

struct Node* node1 = (struct Node*) malloc(sizeof(struct Node*));
                                                  ^^^^^^^^^^^^
struct Node* node2 = (struct Node*) malloc(sizeof(struct Node*));
                                                  ^^^^^^^^^^^^ 

you are incorrectly allocating memory. Instead write

struct Node* node1 = (struct Node*) malloc(sizeof(struct Node));
                                                  ^^^^^^^^^^^ 
struct Node* node2 = (struct Node*) malloc(sizeof(struct Node));
                                                  ^^^^^^^^^^^^  

The same problem exists in the function insert.

Also within the function move the return statement to the end of the function

struct Node* insert(struct Node* rootPtr, struct Node* node) {
    if (rootPtr == NULL) {
        rootPtr = (struct Node*) malloc(sizeof(struct Node));
        rootPtr->data = node->data;
        rootPtr->left = NULL;
        rootPtr->right = NULL;
    }

    if (rootPtr->data > node->data) {
        rootPtr->left = insert(rootPtr->left, node);
    } else if (rootPtr->data < node->data) {
        rootPtr->right = insert(rootPtr->right, node);
    }

    return rootPtr;
}

Pay attention to that passing a pointer to a whole node as the second argument is inefficient and error-prone. You could just pass an integer. So the function should be declared like

struct Node* insert(struct Node* rootPtr, int data );