Segfault when accessing nodes of binary search tree

Question

I am implementing a simple binary search tree in C with the following structs:

typedef struct bstNode{
    double val;
    struct bstNode* left;
    struct bstNode* right; 
} Node;

typedef struct bsTree{
    Node* root;
    size_t size;
} BST;

where BST* createTree(double val) returns a binary search tree struct with the following routine:

BST* createTree(double val){
    Node* root = (Node*) malloc(sizeof(Node));
    root->val = val;
    root->right = NULL;
    root->left = NULL;
    BST* t = malloc(sizeof(BST));
    if(t == NULL){
        free(root);
        free(t);
        return NULL;
    }
    t->root = root;
    t->size = 1;
    return t;
}

Additionally, I have implemented int insert(BST* tree, double in) that inserts a given value as a node into the binary search tree:

int insert(BST* tree, double in){
    if(tree->root == NULL)  return -1;
    Node* curr = tree->root;

    while(curr!=NULL){
        if(curr->val<=in){
            curr = curr->right;
        }else{
            curr = curr->left;
        }
    }

    curr = (Node*) malloc(sizeof(Node));
    if(curr == NULL){
        printf("Could not create new node");
    }
    curr->val = in;
    curr->right = NULL;
    curr->left = NULL;
    tree->size = tree->size + 1;
    return 0;
}

Now if I test the implementation with the following code:

int main(){
    BST* tree = createTree(1.0);
    if(tree==NULL){
        printf("Tree could not be created");
        return -1;
    }

    insert(tree, 2.0);
    printf("%lf\n", tree->root->right->val);
    destroyTree(tree);

    return 0;
}

I get a segmentation fault even though I have successfully created curr inside the insert() function. I tried various things such as already malloc'ing the right and left nodes of root in advance (in the createTree() method), but that didn't work either. What am I doing wrong here?

Answer 1

Newly created Node inside insert is not attached to your tree.

curr is local variable, and when you modify it by curr = (Node*)malloc(sizeof(Node)) it just changes the value of this pointer, but none of nodes in tree will point to this value.

Easy way to fix this is to create temporary pointer which points "parent" of nodes, and add one bool variable which indicates to which node (left or right) of parent new child pointer should be assigned.

int insert(BST* tree, double in){
    if(tree->root == NULL)  return -1;
    Node* curr = tree->root;

    Node* parent = NULL;      // added
    bool addToRight = false;  // added
    while(curr!=NULL){
        parent = curr;
        if(curr->val<=in){
            curr = curr->right;
            addToRight = true; // added
        }else{
            curr = curr->left;
            addToRight = false; // added 
        }
    }

    curr = (Node*) malloc(sizeof(Node));
    if(curr == NULL){
        printf("Could not create new node");
    }
    curr->val = in;
    curr->right = NULL;
    curr->left = NULL;

    if (addToRight)             // added
        parent->right = curr;
    else 
        parent->left = curr;

    tree->size = tree->size + 1;
    return 0;
}

Another solution is to use Node**. In this way you can store address of leaf (left or right) and set it to a value of pointer returned from malloc.

Node** t = NULL; // added
while(curr!=NULL){
    if(curr->val<=in){
        curr = curr->right;
        t = &(curr->right); // added
    }else{
        curr = curr->left;
        t = &(curr->left); // added
    }
}

curr = (Node*) malloc(sizeof(Node));
if(curr == NULL){
    printf("Could not create new node");
}
*t = curr; // added
curr->val = in;
curr->right = NULL;
curr->left = NULL;