0

So I have the following code:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Node
{
    int value;
    Node *left = NULL;
    Node *right = NULL;
    Node(int value)
    {
        this->value = value;
    }
};
struct BST
{
    Node *root = NULL;
    void insert(int value)
    {
        cout<<"Inserting: "<<value<<endl;
        Node *current = root;
        while(current != NULL)
        {
            cout<<"YEA";
            if(value > current->value)
            {
                current = current->right;
            }
            else current = current->left;
        }
        current = new Node(value);
        cout<<"In the node val: "<<current->value<<endl;
        if(root == NULL)
        {
            cout<<"Root is NULL but it shouldn't\n";
        }
        cout<<"Root val: "<<root->value<<endl;

    }
    void remove(int value)
    {
        Node *toReplace = NULL;
        Node *toBeReplacedWith = NULL;
        toReplace = search(value);

        Node *current = toReplace->left;
        if(current == NULL) toBeReplacedWith = toReplace->right;
        else
        {
            while(current->right != NULL)
            {
                current = current->right;
            }
            toBeReplacedWith = current;
        }
        current->value = toBeReplacedWith->value;
        current->left = toBeReplacedWith->left;
        current->right = toBeReplacedWith->right;
        free(toBeReplacedWith);
    }
    Node* search(int value)
    {
        Node *current = root;
        while(current != NULL && current->value != value)
        {
            if(current->value > value) current = current->left;
            else current = current->right;
        }
        if(current == NULL)
        {
            cout<<"The node didn't exist in the BST";
        }
        return current;
    }
    void traverse()
    {
        rec_traverse(root);
    }
private:
    void rec_traverse(Node * current)
    {
        if(current == NULL) return;
        rec_traverse(current->left);
        cout<<current->value<<endl;
        rec_traverse(current->right);
    }
};
int main()
{
    BST tree;
    for(int i = 0; i < 10; ++i)
    {
        tree.insert(i);
    }
    tree.traverse();
    return 0;
}

Can somebody tell me why when inserting an element the root still points to NULL instead to a Node instance? I even check the current pointer for a value and it has but still for some reason root is NULL when it should be the first node to be assigned a value

2 Answers 2

2

Can somebody tell me why when inserting an element the root still points to NULL

Your function BST::insert(int value) at no point modifies root.

That's why root remains NULL.

One way to make your approach work is to have current point to the pointer you want to modify, instead of having current hold a copy of that pointer.

Sign up to request clarification or add additional context in comments.

3 Comments

"We need to go deeper..."
Can you take a look at the modified code? For some reason when executiong line 31, the program crashes and I can't understand why
@user1113314 That's too radical a change to the original question. If you have a new question, you are free to post a new question. Good luck!
1

You are changing the Node* that current is pointing to, but you never touch the root.

current = new Node(value); should be root = new Node(value); if root was null.

Furthermore, as an aside, apart from the question here, your code will be a LOT simpler if you use recursive calls for insertion and deletion (and you wouldn't have to worry about the case when root is pointing to null because it will be implicitly handled)

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.