Removing final node in a BST causing fault

Question

I'm building a binary search tree in C++, it's made of nodes that contain a pointer to a parent, pointers to a left and right children, an integer key, and a template value as below.

template <class T> class Node {
 private:
  Node<T>* parent;
  Node<T>* left;
  Node<T>* right;

  unsigned int key;
  T value;

 public:
  /*constructors, accessors, mutators, rotating functions are here*/

I've got a separate class for the tree itself, which is mainly just for inserting, balancing the tree, searching for and deleting nodes. In this class, the function to delete a node is takes a key and removes that node from the tree. So far, I've verified that all rotation, balancing, insertion, and accessing functions work properly. While creating the function for removing nodes from the tree, I came across an issue while removing the root. Below is the remove function.

//This currently is only for deleting leaf nodes
void remove(unsigned int key) {
  //Find the node being deleted
  Node<T>* delnode = this->select(key);
  if (!delnode) { return; };
  
  //If the value is a leaf node
  if (!delnode->getLeft() && !delnode->getRIght()) {
    //Store the parent node
    Node<T>* parent = delnode->getParent();

    //The node is both root and leaf
    if (!parent) {
      delete delnode;
      return;
    };

    //If the node is not a root, clip the parent connection
    if (delnode->getKey() < parent->getKey()) {
      parent->setLeft(NULL);
      delnode->setParent(NULL);
    } else if (delnode->getKey() > parent->getKey()) {
      parent->setRight(NULL);
      delnode->setParent(NULL);
    };

    //Delete the node now
    delete delnode;
    return;
  };
};

The smallest section of code that reliably causes an error is the following section of the above function.

if (!parent) {
  delete delnode;
  return;
};

The other sections of the code work so far as I can verify, and remove leaf nodes properly. Removing the root of the tree (regardless of whether it used to have children) causes a 'double free();' error when the program exits.

I can't find the mistake in my previous code that would cause this use of 'delete' to throw a 'double free();' error, what could be the cause?

Answer 1

I've got a separate class for the tree itself, ...

Presumably, this class maintains a pointer to the tree:

template <class T>
class BTree
{
    Node<T>* root;
    // ...
}

After function remove deletes a root node, it must set the root pointer to nullptr.

What's happening now is:

1. The root is deleted once, as delnode, in function remove.
2. It is deleted a second time in the destructor of class BTree.

Thus, the double-free error.