I wanted to implement a BST and tried using vector for input

Question

I wanted to implement a BST class with a vector and somehow its not working. I just wanted to know the reason why its not working.

The main reason that I can think of that root in the BST always remain NULL.

I wanted to experiment ways to use classes in data structures.

#include<iostream>
#include<vector>

using namespace std;

class Node{
    public:
    int data;
    Node* left ;
    Node* right ;

    Node(int val){
        data = val;
        left = NULL;
        right = NULL;
    }
};


class BST{
    public:
    Node* root = NULL;

    void insert(Node* r,int data){
        Node* new_node = new Node(data);
        if(r == NULL){
            r = new_node;
        }

        if(data < r->data){
            if(r->left == NULL){
                r->left = new_node;
            }
            else{
                insert(r->left,data);
            }
        }else if(data > r->data){
            if(r->right == NULL){
                r->right = new_node;
            }
            else{
                insert(r->right,data);
            }
        }else{
            return;
        }
        return;
    }

    BST(vector<int> bst_array){
        for(int i = 0; i<bst_array.size(); i++){
            insert(root,bst_array[i]);
        }
    }

    void print_t(Node* r){
        if(r == NULL){
            cout<<"NULL";
            return;
        }
            
        else{
            print_t(r->left);
            cout<<r->data<<" ";
            print_t(r->right); 
        }
    }
    
};


int main(){

    vector<int> v = {1,3,5,44,23,78,21};

    BST* tr = new BST(v);

    tr->print_t(tr->root);

    return 0;
}

There seem to be a logical mistake on my end please help me find it.

Thanks in advance.

Answer 1

The reason is that root is never assigned another value after its initialisation to NULL. Passing root as argument to the insert method can never alter root itself, as it is not the address of root that is passed, but its value.

Some other remarks:

• insert always starts by creating a new node, at every step of the recursion. This is a waste of node creation. In the end you just need one new node, so only create it when its position in the tree has been identified.

• The final else is not needed, as all it does is execute a return, which it would have done anyway without that else block

• As insert is a method of BST, it is a pity that it requires a node as argument. You would really like to just do insert(data) and let it take care of it. For that to happen I suggest to move your insert method to the Node class, where the this node takes over the role of the argument. Then the BST class could get a wrapping insert method that forwards the job to the other insert method.

• Instead of NULL use nullptr.

To solve the main issue, there are many solutions possible. But after making the above changes, it is quite easy to assign to root in the simplified insert method on the BST class.

Here is how it could work:

class Node{
    public:
    int data;
    Node* left ;
    Node* right ;

    Node(int val){
        data = val;
        left = nullptr;
        right = nullptr;
    }

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

class BST {
    public:
    Node* root = nullptr;

    void insert(int data) {
        if (root == NULL) { // Assign to root
            root = new Node(data);
        } else { // Defer the task to the Node class
            root->insert(data);
        }
    }

    BST(vector<int> bst_array){
        for(int i = 0; i<bst_array.size(); i++){
            insert(bst_array[i]); // No node argument
        }
    }

    /* ...other methods ...*/
}