Access violation reading location 0x00000000 in binary search tree

Question

Just showing how the node of the binary tree looks like. I'm not sure what is wrong but I have a feeling it has something to do with the function being private. How I can compare the private data so I can see if the value I am looking for is inside that node?

    class binarytree
    {
    private:
        class node
        {
        public:

            int data;
            node * left;
            node * right;

            node (int x)
            {
                data = x;
                left=NULL;
                right=NULL;
            }


        };

    node * root;

This is how I insert the node

    void insert(int x, node * &r)
        {
            if(r==NULL)
            {
                r= new node(x);
            }

            else
    {
        if(x < r->data)
        {
            //insert left
            insert(x, r->left);
        }

        else
        {
            //insert right
            insert(x, r->right);
        }
    }
}

Here is the part of the code that gives me trouble when I try to compare x to r->data the program crashes and gives me the error message " Access violation reading location 0x00000000"

void remove(int x, node * &r)
{

    if(x == r->data)
    {
        if(r->right == NULL && r->left == NULL)
        {

            r = NULL;

        }

        else if(r->right == NULL && r->left != NULL)
        {
            r = r->left;

        }

        else if(r->right != NULL && r->left == NULL)
        {
            r = r->right;
        }

        else
        {
            node * temp;
            temp =r;
            r = r->left;
            while(r->right != NULL)
            {
                r = r->right;
            }

            r->right = temp->right;
            delete temp;
        }
    }

    else if ( x < r->data)
    {

        remove(x, r->left);

    }

    else if (x > r->data)
    {
        remove(x , r->left);
    }


}

This is where the functions are publicly. Then I call the private functions so I can manipulate the private tree.

public:

    binarytree()
    {
    root =  NULL;
    }

    ~binarytree()
    {
    //tooo: write this
    }

//return true if empty, false if not
    bool empty()
    {}


    void insert(int x)
    {
    insert(x, root);

    }




    void remove(int x)
    {
        remove(x,root);

    }

};

EDIT: Here is another function of the program that works but might be causing r to point to NULL.

    int extractMin(node * &r)
{

    if(r->left == NULL)
    {
        if(r->right == NULL)
        {

            return r->data;

        }

        else
        {
            int x = r->data;
            r = r->right;
            return x;

        }
    }

    else
    {

        return extractMin(r->left);

    }
}

Here is the new function to check to see if r is NULL

    void remove(int x, node * &r)
{
    if(r == NULL)
    {
        cout<<"why am I null?"<<endl;
    }

    else
    {
        if(x == r->data)
        {
            if(r->right == NULL && r->left == NULL)
            {

                r = NULL;

            }

            else if(r->right == NULL && r->left != NULL)
            {
                r = r->left;

            }

            else if(r->right != NULL && r->left == NULL)
            {
                r = r->right;
            }

            else
            {
                node * temp;
                temp =r;
                r = r->left;
                while(r->right != NULL)
                {
                    r = r->right;
                }

                r->right = temp->right;
                delete temp;
            }
        }

        else if ( x < r->data)
        {

            remove(x, r->left);

        }

        else if (x > r->data)
        {
            remove(x , r->left);
        }

    }
}

Answer 1

you should always check for NULL before trying to get to the inner members:

void remove(int x, node * &r)
{
    if(r != NULL)
    {
       // Your code
    }
}

you call to remove with r as NULL and then try to check r.Left. then here you have access violation

also i must ask, did any if this worked for you? specifically insert wont work this way. try

    void insert(int x, node * &r)
    {
        if(r==NULL)
        {
            r= new node(x);
        }
        else
        {
            if(x < r->data)
            {
                if(r->left != NULL)
                {
                   //insert left
                   insert(x, r->left);
                }
                else
                {
                    r->left = new node(x);
                }
            }
            else
            {
                if(r->right != NULL)
                {
                   //insert right
                   insert(x, r->right);
                }
                else
                {
                    r->left = new node(x);
                }

            }
        }
    }

Answer 2

You are comparing x to the root. When your tree is empty, root == nullptr. You should check to see if r == nullptr first, as in:

bool remove(int x, node * &r) {
   if(!r) {
      return false; // Indicate whether removal succeeded
   }

   //... etc.
}

Answer 3

Well it the error says, r is pointing to NULL when you try to derefference it. So you have to make sure when you assign memmory to r it doesn't return NULL.

binarytree()
{
    root =  NULL;
}

void remove(int x)
{
    remove(x,root);

}

In your case you are trying to derefference NULL (as the error says) This happens in your code when you are calling a remove before you have called an insert. You simply should check at the beginning of remove for r isn't pointing to NULL. Or even better, make sure you won't parse in r when its NULL.

Answer 4

r is null somehow. You need to check if the r passed in is NULL, or check if the root is non-null, and call remove on children only if they exist.