Implementation of BST C++ Segmentation Fault

Question

I have implemented binary search tree in C++ and for some reason I am not seeing where the segmentation fault occurs. But I do notice that when I comment out root = node in the first conditional statement in addNode the error goes away. What exactly is a segmentation fault and how does it related to pointers?

#include <iostream>
#include <iomanip>
using namespace std;

class bstNode
{
public:
    int value;
    bstNode *left;
    bstNode *right;

    bstNode(){};
    ~bstNode(){};

    bstNode(int value)
    {
        this->value = value;
        this->left = NULL;
        this->right = NULL;
    }

    bstNode(int value, bstNode *left, bstNode *right)
    {
        this->value = value;
        this->left = left;
        this->right = right;
    }

    bstNode *root;

    void addNode(int value)
    {
        if (root == NULL)
        {
            bstNode *node = new bstNode(value);
            root = node;
        }
        else
        {
            bstNode *focusNode = root;
            bstNode *parent;

            while (focusNode != NULL)
            {
                if (value > focusNode->value)
                {
                    focusNode = focusNode->right;
                    if (focusNode == NULL)
                    {
                        focusNode->right = new bstNode(value);
                    }
                }
                else
                {
                    focusNode = focusNode->left;
                    if (focusNode == NULL)
                    {
                        focusNode->left = new bstNode(value);
                    }
                }
            }
        }
    }

    static void printBST(bstNode *node)
    {
        while (node != NULL)
        {
            printBST(node->left);
            cout << node->value;
            printBST(node->right);
        }
    }
};

int main()
{
    bstNode *node = new bstNode();
    node->addNode(7);
    node->addNode(2);
    node->addNode(18);
    node->addNode(6);
    node->addNode(4);
    node->addNode(23);

    bstNode::printBST(node->root);

    return 0;
}

Answer 1

The immediate error is this

                if (focusNode == NULL) {

                    focusNode->left = new bstNode(value);
                }

this is clearly wrong, if a pointer is null you cannot use it. You have this in multiple places. Fix that and then update the question once you have got past that. How did I know this? I ran your code under my debugger and it told me immediatley, you should learn how to get the most out of your debugger.

Next

void addNode(int value)

as a method for a class defined as

class bstNode {

public:
    int value;

is very bad practice. In that method what does value refer to? The argument or the member variable. Get into the habit of giving member variables specific names like this

class bstNode {

public:
    int value_;

Also minor nits. The accepted style for naming classes is with leading Caps like this

class BstNode {

public:
    int value_;

or even

class BSTNode

class bstNode {

public:
    int value_;

Answer 2

In the the following code...

while(focusNode != NULL){

    if(value > focusNode->value){

        focusNode = focusNode->right;
        if(focusNode == NULL){
            
            focusNode->right = new bstNode(value);
        }
    }
    else{

        focusNode = focusNode->left;
        if(focusNode == NULL){

            focusNode->left = new bstNode(value);
        }
    }

}

...you are referencing the children of a node that is guaranteed to be NULL because you verified that using the conditional statement. Since the node itself does not exist, it doesn't have properties like children. Imagine you're trying to communicate with the child of a person who has never existed.

The variable focusNode stores an address of a node. What focusNode->value does is that it goes to the node whose address focusNode stores and retrieves the value property from there.

When focusNode is NULL, it doesn't point to any node, thus you can't go there and retrieve its value property.

I wrote the code that you can replace with your while loop. I have tested it and it works:

while(true){
    if(value > focusNode->value){

        if(focusNode->right == NULL){
            focusNode->right = new bstNode(value);
            return;
        } else focusNode = focusNode->right;
    }
    else{

        if(focusNode->left == NULL){
            focusNode->left = new bstNode(value);
            return;
        } else focusNode = focusNode->left;
    }

}

I also fixed your printBST function. In the printBST function use if instead of while, because the the code inside the while loop would be executed an infinite number of times instead of printing the BST once.

static void printBST(bstNode* node){

    if(node != NULL){
    
        printBST(node->left);
        cout << node->value <<" ";
        printBST(node->right);
    }
}

Answer 3

using namespace std;

I'd advise against doing this in general. It's hard to be sure what's in namespace std, but the short summary is "a lot, and more all the time", so making all of it visible directly can lead to problems.

bstNode(){};
~bstNode(){};

These don't really accomplish anything useful. The point of a constructor is to initialize the object, but these just leave the object uninitialized, which can lead to problems--especially segmentation faults when/if you try to dereference an uninitialized pointer.

bstNode(int value){

    this->value = value;
    this->left = NULL;
    this->right = NULL;
}

This is better, but I'd prefer to use a member initializer list instead of assignments inside the body of the ctor, and I'd prefer nullptr over NULL:

bstNode(int value) 
    : value(value)
    , left(nullptr)
    , right(nullptr) {}

This next one:

bstNode(int value, bstNode* left, bstNode* right){

    this->value = value;
    this->left = left;
    this->right = right;
}

...is pretty nicely written (though it could also use a member initializer list, which is usually preferable), but only rarely useful when building a binary search tree, because in normal use you only ever insert new leaf nodes, not new internal nodes.

void addNode(int value){

    if (root == NULL){

        bstNode* node = new bstNode(value);
        root = node;
    }
    else{

        bstNode* focusNode = root;
        bstNode* parent;

        while(focusNode != NULL){

            if(value > focusNode->value){

                focusNode = focusNode->right;
                if(focusNode == NULL){
                    
                    focusNode->right = new bstNode(value);
                }
            }
            else{

                focusNode = focusNode->left;
                if(focusNode == NULL){

                    focusNode->left = new bstNode(value);
                }
            }
        }    
    }
}

This is at least one obvious source of a segmentation fault--you dereference a pointer immediately after verifying that it's null.

At least for a first attempt, I think I'd use a recursive implementation, which tends to be simpler:

void addNode(int value, bstNode *&node = root) { 
    if (node == nullptr) {
        node = new node(value);
    } else if (value < node->value) {
        addNode(value, node->left);
    } else if (value > node->value) {
        addNode(value, node->right);
    } else {
        // attempt at inserting duplicate value
    }
}

Note that this passes a reference to a pointer, so we can modify the "current" pointer, rather than having to track the parent pointer while traversing the tree.

static void printBST(bstNode* node){

    while(node != NULL){
        printBST(node->left);
        cout << node->value;
        printBST(node->right);
    }    
}

Since we're doing this recursively, we don't need (or even want) a loop. Traversing the left sub-tree, the current node, and the right subtree traverses the entire tree, with no iteration needed.

Also note that this doesn't print any delimiter between the numbers in the nodes, so a tree containing 12, 34 and a tree containing 1, 2, 3, 4 will both be printed out as 1234, which probably isn't very useful. Fortunately, adding a delimiter is pretty easy.

static void printBST(bstNode* node){

    if (node != nullptr){
        printBST(node->left);
        cout << node->value << ' ';
        printBST(node->right);
    }
}