Binary Search Tree Insertion throws segmentation Fault

Question

Can somebody please explain what is wrong with the below code for binary search insertion?It gives segmentation fault when I try to insert 2nd element.

node * insert(node * root, int value)
{
    if(root == NULL){
        node *newnode = (node *)malloc(sizeof(node));
        newnode->data = value;
        newnode->left = NULL;
        newnode->right = NULL;
        root = newnode;
    }
    else{
        if(root->data > value)
            insert(root->left, value);

        if(root->data < value)
            insert(root->right, value);
    }
   return root;
}

int main(){
    node* root = NULL;
    root = insert(root, 5);
    root = insert(root, 10);
}

Hello, welcome to StackOverflow. Please add the declaration of your node type. Are you sure the root value is modified in your main() function ? — philant, Dec 18 '15 at 09:39
@undur_gongor: then should he not have "root->left=insert(root->left, value);"? I'm confused — BlueMoon93, Dec 18 '15 at 09:49
@BlueMoon93: In some cases, the root node has to be modified. You can do this by passing a pointer to the root pointer or by returning the (possibly modified) root. an111 used the second approach. Currently, the root node is only modified when the tree is empty. Later it might need modification due to re-balancing. — undur_gongor, Dec 18 '15 at 09:51

score 1 · Answer 1 · answered Dec 18 '15 at 09:46

You have to include stdlib.h.

Otherwise, the compiler doesn't know the prototype of malloc and assumes it returns an int rather than a pointer. If your ABI treats pointers and integers differently, this leads to problems.

The corresponding warning is hidden by the cast.

score 1 · Answer 2 · edited May 23 '17 at 12:07

As I see it, there're two possibilities for why this might crash:

as @undur_gongor has pointed out, you're not including stdlib.hand run on an architecture with different sizes for integers and pointers. This would perfectly match a reason for why you shouldn't cast the result of malloc
you're out of memory. Since you don't check the result of malloc it may have failed and returned NULL

Binary Search Tree Insertion throws segmentation Fault

2 Answers2