Segmentation fault Binary search Tree

Question

I know there is few questions with a similar title, however I went over them and still couldn't solve my error.

This is the BST implementation:

struct node {
    int val;
    node* left;
    node* right;
};

node* createNewNode(int x)
{
    node* nn = new node;
    nn->val = x;
    nn->left  = nullptr;
    nn->right = nullptr;

    return nn;
}

void bstInsert(node* &root, int x)
{
    if(root == nullptr) {
        root = createNewNode(x);
        return;
    }

    if(x < root->val)
    {
        if(root->left == nullptr) {
            root->left = createNewNode(x);
            return;
        } else {
            bstInsert(root->left, x);
        }
    }

    if( x > root->val )
    {
        if(root->right == nullptr) {
            root->right = createNewNode(x);
            return;
        } else {
            bstInsert(root->right, x);
        }
    }
}

Here is my main:


int main() {
    node *root = nullptr;
    for (int i = 0; i < 100000; i++) {
        bstInsert(root, i);
    }
}

If I try to insert 10000 elements then it works alright. however when I try to insert 100000 elements I get in the debugger:

Signal = SIGSEGV (Segmentation fault)

It happens when the value of I in the loop reaches 32469, what am I missing ?

H.S. · Accepted Answer · 2022-01-23 03:45:10Z

2

First of all, your Binary Search Tree is Right Skewed Binary tree because the new element will get added as the right most child of existing tree.

That said, for every insertion, the recursion will go as deep as the value of i passed to bstInsert() and, for some big value of i, eventually it run out of space, while recursing, and crash. It's not good idea to use recursion for insertion in such a big tree. Better to go for iterative implementation.

Additional:
Add the check for new operator failure.

PS:
On my system your code is not crashing for 100000 elements insertion :).

edited Jan 23, 2022 at 3:45

answered Jan 23, 2022 at 3:35

H.S.

12.7k2 gold badges17 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Barsloai Over a year ago

Thanks, it is right skewed because I'm trying to measure insertion at an ordered tree at the right most node. You cleared it up for (:

Abdul Rauf · Accepted Answer · 2022-01-23 04:11:50Z

interestingly your code works just fine for me on fedora g++ compiler. it might be my compiler allocates 8Bytes to integer and yours might be allocating 4Bytes to integer so please try this and let me know.

#include <iostream>

struct node {
    long val;
    node* left;
    node* right;
};

node* createNewNode(long x)
{
    node* nn = new node;
    nn->val = x;
    nn->left  = nullptr;
    nn->right = nullptr;

    return nn;
}

void bstInsert(node* &root, long x)
{
    if(root == nullptr) {
        root = createNewNode( x);
        return;
    }

    if(x < root->val)
    {
        if(root->left == nullptr) {
            root->left = createNewNode(x);
            return;
        } else {
            bstInsert(root->left, x);
        }
    }

    if( x > root->val )
    {
        if(root->right == nullptr) {
            root->right = createNewNode(x);
            return;
        } else {
            bstInsert(root->right, x);
        }
    }
}
int main() {
    node *root = nullptr;
    for (long i = 0; i < 100000; i++) {
        bstInsert(root, i);
        std::cout << i << std::endl; // printing output to see the results using short gives overlow.
    }
}

if that does not work than you computer memory is not available as much as required it could be you only have less than 785 KB of CPU CACHE since at runtime program is in cache and with 100000 probably uses ~ 785 KB memory which in this specific case is in cache because it is at runtime and no management applied to it yet.

Collectives™ on Stack Overflow

Segmentation fault Binary search Tree

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related