Problems trying to delete a BST in C++

Question

I want to delete all the nodes in a binary search tree. Here's the code that inserts nodesAmount nodes in the tree:

    void testFindInsert(int nodesAmount) {
    int value; 
    BSTNode* n = NULL;
    BSTNode* root = NULL;

    for (int i = 0; i < nodesAmount; i++) {
        value = rand() % INT_MAX + 1;
        n = new BSTNode(value, "");
        if (!findNode(root, value))
            root = (BSTNode*)insertNode(root, n, BST);
    }

    root->destroy();
    root = NULL;
}

This is part of the BSTNode class:

BSTNode::BSTNode(int value, string str) {
    this->value = value;
    this->str = str;
}
...
void BSTNode::destroy(){
    if (this == NULL) return;
    this->left->destroy();
    this->right->destroy();
    delete this;
}

And here the insert method:

BSTNode* insertNode(BSTNode* root, BSTNode* node, TreeType bstType = BST) {
    bool inserted = false;
    BSTNode* treeIterator = root;
        
    if (root == NULL) {
        root = node;
        inserted = true;
    } 

    while (!inserted) {
        if (node->getValue() < treeIterator->getValue()) {
            if (treeIterator->getLeft() != NULL) {
                treeIterator = treeIterator->getLeft();
            }
            else {
                treeIterator->setLeft(node);
                node->setFather(treeIterator);
                inserted = true;
            }
        }
        else if (node->getValue() > treeIterator->getValue()) {
            if (treeIterator->getRight() != NULL) {
                treeIterator = treeIterator->getRight();
            }
            else {
                treeIterator->setRight(node);
                node->setFather(treeIterator);
                inserted = true;
            }
        }
    }
    return root;
}

All works correctly but, after calling testFindInsert, memory is not released. Even trying in this different way using a stack doesn't resolve the problem:

void testFindInsert(int nodesAmount) {
    int value; 
    BSTNode* n = NULL;
    BSTNode* root = NULL;

    for (int i = 0; i < nodesAmount; i++) {
        value = rand() % INT_MAX + 1;
        n = new BSTNode(value, "");
        if (!findNode(root, value))
            root = (BSTNode*)insertNode(root, n, BST);
    }

    stack<BSTNode*> stackNodes;
    BSTNode* node;
    stackNodes.push(root);

    while (!stackNodes.empty()) {
        node = stackNodes.top();
        stackNodes.pop();
        if (node != NULL) {
            stackNodes.push(node->getRight());
            stackNodes.push(node->getLeft());
            delete node;
        }
    }
    root = NULL;
}

Does anyones know where's the problem? Thanks in advance!

Answer 1

The problem appears to be here:

n = new BSTNode(value, "");
if (!findNode(root, value))
    root = (BSTNode*)insertNode(root, n, BST);

If a node with value value already exists then memory is being wasted by allocating it to n since that node n is not inserted.

So allocate memory for node once sure that the node with value doesn't exist in the BST. Like this:

if (!findNode(root, value)) {
    n = new BSTNode(value, "");
    root = (BSTNode*)insertNode(root, n, BST);
}