CODEWITHSUNDEEP
cpointersbinary-search-tree
齐天大圣
齐天大圣

Reputation: 1189

Implement BST in c: segmentation fault

i'm trying to implement binary search tree in c. I use lldb to trace my code and i found out when the function PUT return, it return a node pointer with key = 5 and value = 9, and it was assigned to the node pointer P in main.

however when i pass it to the tree_walk function and try to print out everything, it gave me a segmentation fault. can anyone please tell what is wrong with my code. Thank you

typedef struct Node{
    int key;
    int value;
    int size;
    struct Node *left;
    struct Node *right;
}Node;

Node* put(Node **node, int k, int val){
    if(*node == NULL){
        Node *newNode = (Node *)malloc(sizeof(Node*));
        newNode->key = k;
        newNode->value = val;
        return newNode;
    }else if((*node)-> key == k){
        (*node)->value = val;
    }else{

        int cmp = k > ((*node)->key) ? 1 : 0;

        Node **ptr = NULL;

        if(cmp == 1){
            ptr = &((*node)->right);
            (*node)->right = put(ptr, k, val);
        }else{
            ptr = &((*node)->left);
            (*node)->left = put(ptr, k ,val);
        }
    }
    (*node)->size = size((*node)->left) + size((*node)->right) + 1;
    return *node;
}

int main(void){

    Node *p = NULL;
    p = put(&p, 5,9);
    tree_walk(p);
}

Upvotes: 0

Views: 82

Answers (1)

M.M
M.M

Reputation: 141633

This line allocates the wrong size:

Node *newNode = (Node *)malloc(sizeof(Node*));

It should be:

Node *newNode = malloc( sizeof *newNode );

You only allocated enough space for a pointer, not for a Node.

Another problem is that you never initialize newNode->left and newNode->right. If the tree_walk function tries to read them then it causes undefined behaviour.

Upvotes: 3

Related Questions