CODEWITHSUNDEEP
csegmentation-faultbinary-search-tree
Mr. Sigma.
Mr. Sigma.

Reputation: 435

Segmentation fault in a function of BST implementation

Here is my implementation to insert an item in a Binary search tree. 

void insert(struct Node* root,int item){
if(root==NULL){
    root = newNode(item); // newNode is a function which creates new node, initialized it with item & return pointer of the new node.
}
if(item < root->item)
    insert(root->left,item);
else
    insert(root->right,item);
}

But I am clueless why it is giving segmentation fault with following invoking in driver program?

struct Node* root = NULL;
insert(root,50);

Upvotes: 0

Views: 94

Answers (1)

Some programmer dude
Some programmer dude

Reputation: 409206

You probably have infinite recursion.

With the initial call then root will be a null pointer, meaning you will create a new root node. Then we get to the check if(item < root->item) which will be false, leading to the program executing the else clause and calling insert recursively.

If newNode sets the left and right pointers to NULL, then the whole thing will start over, creating a new node and going to the else clause and calling itself recursively.

The solution is another else, as in

if (root == NULL) {
    ...
} else if (item < root->item) {
    ...
} else {
    ...
}

You would have found out the problem very quickly if you just used a debugger to either catch the crash or to step through the code. In the future, start by using a debugger first to catch the crash, and locate where and when it happens, and examine the function call stack.

If on the other hand newNode does not initialize the left and right pointers of the node structure, then you will have undefined behavior, which can often lead to crashes.

Dynamic allocation functions like malloc does not initialize the memory it allocates. The contents of the memory is indeterminate. Dereferencing such a pointer leads to said UB (Undefine Behavior).

This too could have been detected quickly with the help of a debugger.

Finally a third possible reason for your crashing, if you fixed the above to problems, is that when you pass an argument to a function in C, it is passed by value. That means the value is copied into the argument, and the argument inside the function is like any other local variable, and all changes to the argument (assignments) are lost once the argument goes out of scope when the function returns.

That means after the initial call to insert the variable root will still be a null pointer.

The solution to this is mentioned in my comment.

Upvotes: 2

Related Questions