Binary Search Tree in C causing a Heap Corruption Error

Question

So I'm a Python programmer and I'm trying to teach myself C. Just as practice, I've been trying to implement a simple Binary Search Tree in C. I've never had to work with memory allocation or pointers before and its been causing a lot of errors.

My program has been giving me exit code -1073740940 (0xC0000374) which I understand means that the heap has been corrupted. It's a bit of a long program, so I just included the offending function.

This insert function is repeatedly called using a for loop to insert the contents of an array into the binary search tree. The array's contents are 5, 4, 6, 3, 7, 2, 8, 1, 9, and 0 (designed to make the tree balanced).

So the function first has 5 passed to it. The pointer called by pBST->listRoot is NULL (pBST is a pointer to a list struct), so insert 5 as a the root node. This works fine. Then 4 is passed to the function. Since there is already a root, it checks the children of that root. 4 is less than 5 so check 5's left child. The pointer for 5's left child is null, so it attempts to insert 4 as a new node. This is the line that crashes the program:

struct Node* pTemp = calloc(1, sizeof(struct Node));

I've tried a couple variations of this line. Here's the kicker: cLion's debugger cannot reproduce this. When I run it through the debugger, it works perfectly. I think it has to do with the fact that the debugger uses the same memory addresses every time for reproducibility. I left the debugging printf statements and added the code for the Node and binarySearchTree structs.

typedef struct Node BSTNode;

struct Node {
    BSTNode* parent;
    BSTNode* left;
    BSTNode* right;
    int* data;
};



typedef struct {
    BSTNode* listRoot;
    int nodeCount;
} binarySearchTree;

void insert(int Value, binarySearchTree* pBST) {
/*
 * This function
 */

//====DEBUG CODE============
int debugIterations = 0;
printf("Now inserting %d \n", Value);
//=====END DEBUG CODE=======


//if no root, make it the root
if (pBST->listRoot == NULL) {

    struct Node* newNode = calloc(1, sizeof(binarySearchTree));
    (*pBST).listRoot = newNode;

    (*pBST).listRoot->data;

    (*pBST).listRoot->data = Value;
    //pBST->listRoot->data = Value;

    pBST->listRoot->parent = NULL;

    pBST->listRoot->right = NULL;
    pBST->listRoot->left = NULL;

    return;
} else {
    struct Node* pCursor = pBST->listRoot;

    while (1){

        printf("Iterations: %d \n", debugIterations);
        debugIterations++;


        //Check if the number is the same
        if (pCursor->data == Value){
            printf("ERROR: Tried to insert duplicate value into tree");
            return;
        }

        //Is the value > the node?
        else if (pCursor->data < Value) {

            //DEBUG
            printf("== check succeeded, now value > data\n");


            // Is the value a Null?
            if (pCursor->right == NULL) {

                //DEBUG
                printf("Running function to insert %d as a new node to the right\n", Value);

                //If yes, then insert the value as a nul

                //Create Node
                struct Node* pTemp = calloc(1, sizeof(binarySearchTree));
                pTemp->data = Value;
                pTemp->parent = pCursor;
                pCursor->right = pTemp;
                pTemp->left = NULL;
                pTemp->right = NULL;

                return;
            }

            //If no, then iteravely continue.
            else {

                printf("Iteravely continuing to the right");

                pCursor = pCursor->right;
                continue;
            }

        }

        //Is the value < the root?
        else {

            //DEBUG
            printf("== check succeeded, now value < data\n");



            //Is the value a Null?
            if (pCursor->left == NULL) {

                //DEBUG
                printf("Running function to insert %d as a new node to the left\n", Value);




                //If yes, then insert the value where the null is.
                //Create Node

                struct Node* pTemp = (struct Node*)calloc(1, sizeof(struct Node));

                printf("Successfully declared and allocated memory");

                pTemp->data = Value;
                pTemp->parent = pCursor;
                pCursor->left = pTemp;
                pTemp->left = NULL;
                pTemp->right = NULL;

                return;
            }

            //If no, then iteravely continue
            else{

                printf("Iteravely continuing to the right");

                pCursor = pCursor->left;
                continue;
            }

        }

    }

}

}

Answer 1

The line

struct Node* pTemp = calloc(1, sizeof(binarySearchTree));

is wrong. The structure binarySearchTree has one pointer and one int, but the structure struct Node has 4 pointers, so struct Node should be larger than binarySearchTree and this allocation will allocate less space than required, leading to out-of-range access.

It should be:

struct Node* pTemp = calloc(1, sizeof(*pTemp));

or

struct Node* pTemp = calloc(1, sizeof(struct Node));

Also it looks very weird to store the data int Value in the member int* data; with (*pBST).listRoot->data = Value;. It looks like the member should be int, not int*.