Problem with Binary Search tree code for insert operation

Question

I am unable to access the left,right nodes from my root node in my insert function as evidenced by the terminal output. What is causing the error.

Code Body:

#include<iostream>

class Node {
    public:
    int key; int data;
    Node * left;
    Node* right;
    Node (int key, int data):key(key),data(data),right(nullptr),left(nullptr){std::cout<<"ooga booga"<<std::endl;}

    //Recursive function to insert an key into BST
    void insert( int key,int data)
    {
        std::cout<<"reached here.Current node now has key="<<this->key<<" while input key is "<<key <<std::endl;
        // if the root is null, create a new node an return it
        if (this == nullptr)
        {
            std::cout<<"in 1st if block "<<this->key<<std::endl;    
            this->key=key;
            this->data=data;
            return;
        }

        // if given key is less than the root node, recur for left subtree
        if (key < this->key)
        {   
            std::cout<<"in 2nd if block "<<this->key<<std::endl;    
            left->insert(key, data);
            std::cout<<"in else block 2"<<this->key<<std::endl;
        }

        // if given key is more than the root node, recur for right subtree
        else
        {
            std::cout<<"in else block "<<this->key<<std::endl;  
            right->insert(key, data);}
            std::cout<<"in else block 2"<<this->key<<std::endl; 
            return;
        }

// A utility function to do inorder traversal of BST 
void inorder() 
{ 
    if (this != nullptr) 
    { 
        this->left->inorder(); 
        printf("%d \n", this->key); 
        this->right->inorder(); 
    } 
} 



};


// Driver Program to test above functions 
int main() 
{ 
    /* Let us create following BST 
              50 
           /     \ 
          30      70 
         /  \    /  \ 
       20   40  60   80 */
    Node *root=new Node(50,10); 
    std::cout<<root<<std::endl;
    std::cout<<root->left<<std::endl;
    //root=nullptr;
    std::cout<<"reached here"<<std::endl;
    std::cout<<"reached here.Root now has key="<<root->key<<std::endl;
    root->insert( 0,10); 
    root->insert( 20,10); 
    root->insert( 40,10); 
    root->insert( 70,10); 
    root->insert(  60,10); 
    root->insert( 80,10); 
    std::cout<<"reached here 2"<<std::endl;
    // print inoder traversal of the BST 
    root->inorder(); 

    return 0; 
}

Output:

ooga booga
0x7fffc10c6e70
0
reached here
reached here.Root now has key=50
reached here.Current node now has key=50 while input key is 0
in 2nd if block 50
Segmentation fault (core dumped)

after checking that this is a nullptr, why do you immediately then try to access its data member this->key? You just checked that it is nullptr. this->key doesn't exist. — MPops
– MPops, Commented Nov 26, 2019 at 21:00
Hi, that was jus an extra debug statement I put in to see how deep the program run before encountering the segmentation fault. — LearningCurve
– LearningCurve, Commented Nov 26, 2019 at 21:05
Try your code on a single node tree. You will probably see it doesn't work either, which means you really didn't test your tree on the simplest of cases (a single node). — PaulMcKenzie
– PaulMcKenzie, Commented Nov 26, 2019 at 21:06
after initializing each Node object with left=nullptr and right=nullptr, why do you then try to access left->insert? left is nullptr. nullptr does not have a left member. — MPops
– MPops, Commented Nov 26, 2019 at 21:06

MPops · Accepted Answer · 2019-11-26 21:08:33Z

1

General summary:

You are creating Node objects with left=nullptr and right=nullptr.

You are never actually initializing these left and right pointers to a new Node.

Before trying to access left->insert, you must first create a new Node.

answered Nov 26, 2019 at 21:08

MPops

3653 silver badges8 bronze badges

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

1 Comment

LearningCurve Over a year ago

yes that was the root cause. As nullptr, left did not have any identity as being a node* pointer. Thus the compiler could not properly allocate the insert () function to it

LearningCurve · Accepted Answer · 2019-11-26 21:27:38Z

0

So this is the only change made to the insert function based on MPops reply which now works:

void insert( int key,int data)
{
    if (key < this->key) {
        if(this->left ==nullptr)
            { left=new Node(key,data); return;}
        else 
            left->insert(key,data);
    }

    else {
        if(this->right ==nullptr)
            { right=new Node(key,data); return;}
        else 
            right->insert(key,data);
    }


}

answered Nov 26, 2019 at 21:27

LearningCurve

356 bronze badges

Collectives™ on Stack Overflow

Problem with Binary Search tree code for insert operation

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