c++ - What is wrong with my binary search tree insertion logic?

binarysearch.h :

    #ifndef BST_BINARYSEARCH_H
    #define BST_BINARYSEARCH_H

    struct Node{
        int value;
        Node* left;
        Node* right;
    };


    class BST{
    public:
        Node* root;
        BST(){
            root = nullptr;
        }
        Node* insertNode(Node* root, Node toInsert);
        void inOrder(Node* root);
    };


    #endif //BST_BINARYSEARCH_H

binarysearch.cpp :

    #include 
    #include 

    #include "binarysearch.h"

    Node* BST::insertNode(Node* root, Node toInsert) {
        if(root == nullptr){
            root = &toInsert;
        }
        else {
            if (toInsert.value value)
                root->left = insertNode(root->left, toInsert);
            else

                root->right = insertNode(root->right, toInsert);
        }
        return root;
    }

    void BST::inOrder(Node *root) {
        if(root!= NULL){
            inOrder(root->left);
            std::coutvalue;
            inOrder(root->right);

        }
    }

main.cpp:

    #include 

    #include "binarysearch.h"

    int main() {

        BST bst;
        Node* root = nullptr;

        Node a;
        a.value = 4;
        a.left = NULL;

        a.right = NULL;

        root = bst.insertNode(root, a);
        bst.insertNode(root, a);
        a.value = 5;
        bst.insertNode(root, a);
        a.value = 6;
        bst.insertNode(root, a);
        a.value = 7;
        bst.insertNode(root, a);

        a.value = 8;
        bst.insertNode(root, a);

        bst.inOrder(root);
        return 0;
    }

Apparently my root keeps moving from the original position as I insert more items.

I am getting Process finished with exit code 139 (interrupted by signal 11: SIGSEGV) on bst.inOrder(root).

What is the issue here?

Answer

The issue is with the insert node function, here you say if the tree is empty, we set the root to be the address of "toInsert". The problem here is toInsert isn't a reference, it's passed by copy. Which means toInsert is a temporary local copy variable, which expires as soon as the function ends. Meaning your root pointer now doesn't point to anything.

   //NOTE: Passing toInsert, copy is made
   Node* BST::insertNode(Node* root, Node toInsert) {
        //NOTE: root is null, so we set it to point to the node's copy

        if(root == nullptr){
            root = &toInsert;
        }
      //NOTE: The copy is destroyed because we ran out of scope
    }

Solution would be to make "toInsert" a pointer, or a reference