Implement BST in c: segmentation fault

Question

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);
}

`put` never changes `*node` so it would make the code a lot simpler to change it to take `Node *node` — M.M, Mar 17 '15 at 04:44
@MattMcNabb isn't just using pointer giving me segmentation fault ? cause i'm manipulating a pointer so i need to pass a pointer to pointer. — 齐天大圣, Mar 17 '15 at 04:48
You aren't manipulating the pointer, you only change things it points to — M.M, Mar 17 '15 at 05:03
@MattMcNabb Hi, my original thought was: since i need to manipulate a pointer that pointers to a struct, so that is why i make my put function take a pointer to pointer, cause c is pass by value. If i pass a pointer I'm just passing a copy. So i don't understand why you said its better to take Node *node. Correct me if I'm wrong. :) — 齐天大圣, Mar 17 '15 at 05:10
Yes you would be passing a copy, but that's correct. You never change the copy, you only change the things pointed to by the copy. Make sure you clearly distinguish in your head between *the pointer* and *the thing the pointer is pointing to*. If you copy a pointer, then both pointers still point to the same place. — M.M, Mar 17 '15 at 05:42

M.M · Answer 1 · 2015-03-17T05:05:44.110

3

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.

edited Mar 17 '15 at 05:05

answered Mar 17 '15 at 04:46

M.M

138,810
21
208
365

Thank you for your help. but why *newNode instead of Node? – 齐天大圣 Mar 17 '15 at 04:53
And i am still getting segmentation fault – 齐天大圣 Mar 17 '15 at 04:54
@Jackddddd it helps to avoid errors like you just made. [see here](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) for further reading. – M.M Mar 17 '15 at 04:59
1

There could be a bug in `tree_walk`. At any rate, [debug your code](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/), don't just dump a big blob of code and say "i get a segfault". There's a lot of investigation you could do before resorting to that. – M.M Mar 17 '15 at 05:04

Implement BST in c: segmentation fault

1 Answers1