Segmentation fault is coming due to constructor

Question

I wrote a C++ code to build binary search tree. Code compiled correctly, but when I try to run the executable its giving segmentation fault. Below is my code:

    #include <iostream>

using namespace std;

struct Node{
    Node *parent, *right, *left; 
    int data;
};

class bst{
    private:
    Node* root;

    public:
        bst (int data);
        void insert (Node * node, int data);
        void insert (int data);
        Node * search (int data);
        Node * search (Node * node, int data);
        // remove (Node * node, int data);
};

bst::bst (int data){
    root -> data = data;
}

void bst::insert (Node * node, int data){
    if (node == NULL){
        node -> data = data;
    }
    else if (data < node -> data){
        insert (node -> left, data);
    }
    else if (data > node -> data){
        insert (node -> right, data);
    }
}

void bst::insert (int data){
    insert (root, data);
}

Node * bst::search (Node * node, int data){
    if (node == NULL || node -> data == data)
        return node;
    else if (data < node -> data)
        return search (node -> left, data);
    else if (data > node -> data)
        return search (node -> right, data);
}

Node * bst::search (int data){
    search (root, data);
}

int main(){
    cout << "main entry\n";
    bst __bst (10);
    cout << "new causing problem\n";
    bst bst2(1);
//  bst *my_bst = new bst(10);
    cout << "tree created\n";
/*  my_bst -> insert(32);
    my_bst -> insert(3);
    my_bst -> insert(36);
    my_bst -> insert(93);
    my_bst -> insert(23);
    cout << "insertion completed\n";

    if (my_bst -> search(4) == NULL )
        cout << "4 does not exist\n";
    if (my_bst -> search(36) != NULL)
        cout << "36 exists in tree\n";
*/  return 0;
}

While debugging for the problem, I cam across an interesting observation. When main function contains only bst __bst (10); object definition and "new causing problem\n" comment after that, it does not print anything. So I assumed that the first object definition is causing problems. But when I put bst bst2(1); or bst *my_bst = new bst(10); in the main, segmentation fault happens again but not before "new causing problem\n" is printed. So execution did go upto that point. So first object definition did not cause any problem in this case.

Can someone tell what caused segmentation fault and why is this strange thing happening.

Edit: As all of you pointed out that I am trying to dereference a NULL pointer during constructor code, I did the suggested changes and code worked fine. But I have a similar program which is working even without those changes. Below is the code for that:

#include <iostream>

using namespace std;

struct Name{
    string first_name;
    string last_name;
};

class Person{
    public:
    Person (string first_name, string last_name){
            name -> first_name = first_name;
            name -> last_name = last_name;
    }   

    int get_age(){
            return age;
    }   

    void set_age (int new_age){
            age = new_age;
    }   

    string get_first_name(){
            return name -> first_name;
    }   

    string get_last_name(){
            return name -> last_name;
    }   

    private:
    Name * name;
    int age;
};

int main (){ 
    Person prince ("Prince", "Kumar");
    cout << prince.get_first_name() << endl;
    cout << prince.get_age() << endl;
    return 0;
}

In this case the program runs perfectly fine. Did the default constructor for Name allocated some space to the name pointer. I knew that it allocates 0 values to numeric types and NULL to pointer, object and strings. Am I right?

Answer 1

private:
    Node* root;

root is not initialized in the constructor

bst::bst (int data){
    root -> data = data;
}

Answer 2

You are dereferencing a null pointer in the insert() when tree empty case

Answer 3

In your constructor you are dereferencing the root which is a pointer without assigning any memory to it, this is undefined behavior:

bst::bst (int data){
  root -> data = data;
}

Something like this would be sufficient:, for this issue

bst::bst (int data) : root( new Node ) 
                      ^^^^^^^^^^^^^^^^ 
{
  root -> data = data;
}

Just use the initialization list to allocate memory. Your insert method also has the same issue:

if (node == NULL){
    node -> data = data;
}

The solution is similar:

node = new Node ;
node->data = data ;

For this to work though you need to initialize right, left and parent correctly, I would advise a constructor in Node for this:

Node() : parent(NULL), right(NULL), left(NULL) {}

These fixes seem to get you a working program.