Error when working with pointer to a pointer in Binary Search Tree functionality

Question

I've got the following code:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Node
{
    int value;
    Node *left, *right;
    Node(int value, Node *l = NULL, Node *r = NULL)
    {
        this->value = value;
        left = l;
        right = r;
    }
};
struct BST
{
    Node *root = NULL;
    void insert(int value)
    {
        cout<<"Inserting: "<<value<<endl;
        Node **current = &root;
        while(*current != NULL)
        {
            if(value >= (*current)->value)
            {
                current = &((*current)->right);
            }
            else current = &((*current)->left);
        }
        (*current) = new Node(value);
    }
    void remove(int value)
    {
        Node *toRemove = search(value);
        remove(toRemove);
    }
    void remove(Node *toReplace)
    {
        if(toReplace == NULL) return;
        Node *toBeReplacedWith = NULL;

        if(toReplace->left == NULL && toReplace->right == NULL)
        {
            delete toReplace;
            toReplace = NULL;
            return;
        }
        if((toReplace->left == NULL) ^ (toReplace->right == NULL))
        {
            if(toReplace->left != NULL) toBeReplacedWith = toReplace->left;
            else toBeReplacedWith = toReplace->right;
            copyAndDeleteNode(toReplace, toBeReplacedWith);
            return;
        }
        Node *current = toReplace->left;
        while(current->right != NULL) current = current->right;
        toReplace->value = current->value;
        remove(current);
    }
    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 copyAndDeleteNode(Node *toReplace, Node *toBeReplacedWith)
    {
        toReplace->value = toBeReplacedWith->value;
        toReplace->left = toBeReplacedWith->left;
        toReplace->right = toBeReplacedWith->right;
        delete toBeReplacedWith;
        toBeReplacedWith = NULL;
    }
    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);
    }
    Node  *a = tree.search(6);
    cout<<"found val: "<<a->value<<endl;

    tree.remove(5);
    tree.remove(9);
    tree.remove(2);
   // tree.insert(4);
    //tree.insert(15);
    tree.insert(6);
    tree.insert(22222);
    cout<<"Traversing:\n";
    tree.traverse();
    return 0;
}

For some reason when executing, the program crashes on the insert(22222) while there is no problem on the previous calls and I can't understand why. The problem must be between lines 26-30 and I always put NULL values in the Node constructor so I'm confused why the loop doesn't break.

Answer 1

One thing right away that is wrong is this:

remove(Node* toReplace).

That function does not update your Node pointer, as you are passing the pointer by value. All of that code within that function that changes the toReplace pointer in any way is thrown away as soon as remove returns.

For example, these lines:

delete toReplace;
toReplace = NULL;

The delete is done, but setting the pointer to NULL does nothing, as again, the toReplace is a local variable.

You need to change your prototype to this:

remove(Node *& toReplace).

Passing a reference to the pointer now allows the pointer value to be updated and be reflected back to the caller.

Also, you did not check your tree's state after you removed the leaf node of '9'. If you did that, you should have clearly seen that your new leaf node of '8' has a bad "right" pointer. This causes all sorts of problems when you attempt to add a node (22222) that is greater than 8.

Your remove function is faulty right here:

    if(toReplace->left == NULL && toReplace->right == NULL)
    {
        delete toReplace;
        toReplace = NULL;
        return;
    }

OK, so you removed the node (assume it is the '9' node). So what about the node that used to point to '9'? You didn't adjust its right (or left) pointers to now point to NULL. That's where the problem starts.

All of these could have been detected if you merely looked at your tree to see if it is still correct after each operation. You could have just used the debugger, or even just printed out the state of the tree at each stage.

Lastly, your tree struct lacks a destructor. You allocate memory, but nowhere is it deallocated.

Edit:

What is this line supposed to do? More specifically, what is that ^ supposed to do?

if((toReplace->left == NULL) ^ (toReplace->right == NULL))