Using "delete" on one pointer deletes a second pointer (Binary Search Tree)

Question

It's an assignment; I can't use smart pointers. Here is a visual representation of what I feel like is going on:

Tree in Debugger after using myTree.remove(4) from Main.cpp:

When I call delete temp in my Binary Search Tree's removeRec function, BTNode* x goes from correctly pointing to 2 to incorrectly being assigned to a random memory like temp. Obviously, I want 4 to disappear and for BTNode* x to point to 2. Is it a problem with my constructor/destructors?

Standalone RemoveRec Function:

bool BinarySearchTree::remove(int data){
    return removeRec(root, data);
}

bool BinarySearchTree::removeRec(BTNode* &x, int data){
    if (x == NULL){
        return false;
    }
    else {
        if (data < x->data){
            return removeRec(x->left, data);
        }
        else if (data > x->data){
            return removeRec(x->right, data);
        }
        else // Found item
        {
            BTNode* temp = x;
            if (x->left == NULL){
                x = x->right;
            }
            else if (x->right == NULL){
                x = x->left;
            }
            else {
                replaceParent(temp, temp->left);
            }
            delete temp;
            return true;
        }
    }
}

BinarySearchTree.h:

#pragma once
#include <cstddef>
using namespace std;

#ifndef BTNODE_H
#define BTNODE_H

struct BTNode{
    // Data Fields
    int data;
    BTNode* left;
    BTNode* right;

    // Constructor
    BTNode(const int& the_data,
        BTNode* left_val = NULL,
        BTNode* right_val = NULL) :
        data(the_data), left(left_val), right(right_val) {}

    // Destructor (to avoid warning message)
    ~BTNode() {
        if (this->left){
            delete this->left;
        }
        if (this->right){
            delete this->right;
        }
    }
};
#endif

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

class BinarySearchTree
{
private:
    BTNode* root;

public:

    // BST Constructor / Deconstructor
    BinarySearchTree() : root(NULL){}

    BinarySearchTree(const int& the_data,
        const BinarySearchTree& left_child = BinarySearchTree(),
        const BinarySearchTree& right_child = BinarySearchTree()) :
        root(new BTNode(the_data, left_child.root, right_child.root)){}

    virtual ~BinarySearchTree(){}

    // Interface Functions ----------------------
    bool add(int data);
    bool remove(int data);
    void clear();

    // My Functions -----------------------------
    bool addRec(BTNode* &x, int data);
    bool removeRec(BTNode* &x, int data);
    bool Search(BTNode* root, int data);
    void replaceParent(BTNode* &old_root, BTNode* &local_root);
};
#endif

BinarySearchTree.cpp:

#pragma once
#include "BinarySearchTree.h"
#include <memory>
#include <thread>
#include <chrono>
#include <mutex>

// Interface Functions ----------------------
bool BinarySearchTree::add(int data){
    return addRec(root, data);
}

bool BinarySearchTree::addRec(BTNode* &x, int data){
    if (x == NULL){
        x = new BTNode(data);
        return true;
    }
    if (data == x->data){
        return false;
    }
    if (x != NULL){
        if (data < x->data){
            return addRec(x->left, data);
        }
        if (data > x->data){
            return addRec(x->right, data);
        }
    }
}

bool BinarySearchTree::remove(int data){
    return removeRec(root, data);
}

bool BinarySearchTree::removeRec(BTNode* &x, int data){
    if (x == NULL){
        return false;
    }
    else {
        if (data < x->data){
            return removeRec(x->left, data);
        }
        else if (data > x->data){
            return removeRec(x->right, data);
        }
        else // Found item
        {
            BTNode* temp = x;
            if (x->left == NULL){
                x = x->right;
            }
            else if (x->right == NULL){
                x = x->left;
            }
            else {
                replaceParent(temp, temp->left);
            }
            delete temp;
            return true;
        }
    }
}

void BinarySearchTree::replaceParent(BTNode* &old_root, BTNode* &local_root){
    if (local_root->right == NULL){
        replaceParent(old_root, local_root->right);
    }
    else{
        old_root->data = local_root->data;
        old_root = local_root;
        local_root = local_root->left;
    }
}

void BinarySearchTree::clear(){
    delete root;
    root = NULL;
}

// My Functions -----------------------------
bool BinarySearchTree::Search(BTNode* root, int data) {
    if (root == NULL) {
        return false;
    }
    else if (root->data == data) {
        return true;
    }
    else if (data < root->data) { // had <= instead
        return Search(root->left, data);
    }
    else if (data > root->data) { // had no "if"
        return Search(root->right, data);
    }
}

Main.cpp

#include <stdio.h>
#include "BinarySearchTree.h"

using namespace std;

int main(){
    BinarySearchTree myTree;

    myTree.add(6);
    myTree.add(4);
    myTree.add(8);
    myTree.add(2);

    myTree.remove(4);
}

Answer 1

When a node is removed from your tree, you reassign the node that pointed to it to now point to a child. In this case, it goes from 6->4->2 to 6->2. However, when you delete the node 4, it is still pointing at 2. Then 4's destructor kills node 2.

The solution is to set both left and right pointers in a node to NULL before you delete it.