Implementing Binary Search Tree in C++, search does not work. Trying to print the elements of the node causes output to crash

Question

I am trying to implement Binary Search Tree in C++. This is the code I wrote. After giving a few inputs when I try to search for them, the output comes out "false" in every case except the value of the root node. When I tried to check if the loop was matching the values in the nodes properly, the programs crashes. However, without printing, the program would just output negative without crashing. Where did I mess up here?

#include<iostream>
using namespace std;

struct tree {
    int data;
    tree* left;
    tree* right;
};

class BST{

public:
    tree* rootTreeNode = NULL;

    tree* createNode(int incomingData){
        tree* newNode = new tree();
        newNode->data = incomingData;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

    void insert(tree* RootAddress, int DataToInsert){
        if(RootAddress == NULL) {
            if(rootTreeNode == NULL) {
                rootTreeNode = createNode(DataToInsert);
            }
            else {
                RootAddress = createNode(DataToInsert);
            }
        } else if(DataToInsert > RootAddress->data) {
            insert(RootAddress->right, DataToInsert);

        } else if(DataToInsert <= RootAddress->data) {
            insert(RootAddress->left, DataToInsert);
        }
    }



    bool search(tree* rootAdd, int dataToSearch){

        if(rootAdd == NULL) {
            return false;
        }

        else if(rootAdd->data == dataToSearch){
            return true;
        }
        else if(dataToSearch > rootAdd->data ){
            search(rootAdd->right, dataToSearch);
        }
        else if(dataToSearch <= rootAdd->data){
            search(rootAdd->left, dataToSearch);
        }
        return false;
    }


    void disp(){
        tree * curr = rootTreeNode;

        while(1){
            cout << curr->data <<endl;

            int ch;

            cout << "Enter 1 for left and 2 for right" <<endl;
            cin >> ch;

            if(ch == 1){
                curr = curr->left;
            }else if(ch == 2){
                curr = curr->right;
            } else if(ch == 3){
                break;
            }
        }
    }

};




int main() {
    BST BinartSearchTree;

    while(1) {
    int c;
    cout << "Enter (1) to insert a value.\nEnter (2) to search value.\nEnter (3) to Check the tree.\n.=> ";
    cin >> c;

    if(c == 1){
        int input;
        cout << "Enter your Data: ";
        cin >> input;

        BinartSearchTree.insert(BinartSearchTree.rootTreeNode, input);

    } else if(c==2){
        int x;
        bool result;
        cout << "Enter element you wanna search: ";
        cin >> x;
        result = BinartSearchTree.search(BinartSearchTree.rootTreeNode, x);
        if(result) {
            cout << "The given data Exists in the tree\n\n";
        } else {
            cout <<"The Data ain't in the tree\n\n";
        }
    } else if(c==3){
        BinartSearchTree.disp();
    }


    }
}

Answer 1

In

void insert(tree* RootAddress, int DataToInsert)

tree* RootAddress is passed by value. "Wait a sec!" You say. "That's a pointer dude! Get off the crack!" The tree pointed at, if there is one, is passed by reference, but the pointer itself... is just a copy.

This means

RootAddress = createNode(DataToInsert);

assigns the new tree to a copy. The source tree has no idea that the copy is now pointing somewhere else.

Solution:

void insert(tree* & RootAddress, int DataToInsert)

Pass the pointer by reference.

Next,

search(rootAdd->right, dataToSearch);

does nothing with the value returned by search Whether the value was found or not the function falls through to

return false;

and always returns false for any node past the first. Not very useful.

Solution:

bool search(tree* rootAdd, int dataToSearch){

    if(rootAdd == NULL) {
        return false;
    }

    else if(rootAdd->data == dataToSearch){
        return true;
    }
    else if(dataToSearch > rootAdd->data ){
        return search(rootAdd->right, dataToSearch);
    }
    else if(dataToSearch < rootAdd->data){
        return search(rootAdd->left, dataToSearch);
    }
}

Other notes:

void disp()

does not check to make sure the iteration does not walk off the end of the tree. A test that curr is not NULL is necessary before cout << curr->data <<endl;

In addition the directing of tree iteration is going to make debugging exceptionally annoying. If this is part of a class assignment, check with the instructor that this is what they really want. If this is for your own nefarious purposes, you are probably better served by implementing one of the common traversal algorithms and printing the whole list.

and

Consider replacing tree* createNode(int incomingData) with a suitable Tree constructor

tree(int incomingData): data(incomingData), left(nullptr), right(nullptr)
{

}

or aggregate initialization

rootTreeNode = new tree{DataToInsert, nullptr, nullptr};

Answer 2

Methinks you might have the wrong inequality in the third "else" of your search function: else if(dataToSearch >= rootAdd->data){ search(rootAdd->left, dataToSearch);