c++memory-leaksbinary-search-tree

Binary search tree memory leak adding residual child nodes to new trees


I'm having two issues with my code; I'd post them as two separate questions, but I believe one is causing the other. The first involves insertion; from my amateur eyes, the insert code seems to be airtight, but in a mere 17 calls to the insert function, Valgrind is detecting 1,496 bytes lost to the ether.

The second issue involves deleting nodes. Deletion itself works just fine, but deconstructing the tree and building a new one leaves the node's children dangling off the root. It even ignores if said child is identical to the root node.

Here's the code to the insert and delete functions; the delete function is split up into two separate functions because that's what the .h file requires.

template <typename SomeType>
void BSTree<SomeType>::Insert(BSTreeNode<SomeType>*& ptr, SomeType item) {
    if (rootPtr == NULL) {
        rootPtr = new BSTreeNode<SomeType>;
        rootPtr->data = item;
        return;
    }
    if (ptr->data < item) {
        if (ptr->rightPtr == NULL) {
            ptr->rightPtr = new BSTreeNode<SomeType>;
            ptr->rightPtr->data = item;
            return;
        } else {
            Insert(ptr->rightPtr, item);
        }
    } else if (ptr->data > item) {
        if (ptr->leftPtr == NULL) {
            ptr->leftPtr = new BSTreeNode<SomeType>;
            ptr->leftPtr->data = item;
            return;
        } else {
            Insert(ptr->leftPtr, item);
        }
    } else if (ptr->data == item) {
        throw FoundInBSTree();
    }
}

template <typename SomeType>
void BSTree<SomeType>::Delete(BSTreeNode<SomeType>*& treePtr, SomeType& item) {
    if (treePtr == NULL)
        throw NotFoundBSTree();
    else if (treePtr->data > item)
        Delete(treePtr->leftPtr, item);
    else if (treePtr->data < item)
        Delete(treePtr->rightPtr, item);
    else
        DeleteNode(treePtr);
}

template <typename SomeType>
void BSTree<SomeType>::DeleteNode(BSTreeNode<SomeType>*& treePtr) {
    if (treePtr == NULL) {
        delete treePtr;
        return;
    }
    if (treePtr->leftPtr == NULL) {
        BSTreeNode<SomeType>* tmp = treePtr;
        treePtr = treePtr->rightPtr;
        delete tmp;
        return;
    } else if (treePtr->rightPtr == NULL) {
        BSTreeNode<SomeType>* tmp = treePtr;
        treePtr = treePtr->leftPtr;
        delete tmp;
        return;
    } else {
        treePtr->data = GetPredecessor(treePtr->leftPtr);
        Delete(treePtr->leftPtr, treePtr->data);
    }
    if (treePtr == NULL) {
        delete treePtr;
        return;
    }
}

EDIT: The memory leaks aren't coming from the Delete code. Valgrind says that everything is caused by Insert. Maybe the issue is the destructor, which calls this function at the root and then deletes the root.

template <typename SomeType>
void BSTree<SomeType>::Destroy(BSTreeNode<SomeType>*& ptr){
    if(ptr == NULL) return;
    Destroy(ptr->leftPtr);
    delete ptr->leftPtr;
    Destroy(ptr->rightPtr);
    delete ptr->rightPtr;
    ptr = NULL;
}

EDIT 2: Alright, let's see if this is good enough for an MRE.

template <typename SomeType>
SomeType BSTree<SomeType>::GetPredecessor(BSTreeNode<SomeType>* treePtr) const{
    BSTreeNode<SomeType>* tmp = treePtr;
    while(tmp->rightPtr != NULL){
        tmp = tmp->rightPtr;
    }
    return tmp->data;
}

template <typename SomeType>
BSTree<SomeType>::BSTree(){
    rootPtr = NULL;
}

template <typename SomeType>
BSTree<SomeType>::~BSTree(){
    Destroy(rootPtr);
    delete rootPtr;
}
  
template <typename SomeType>
void BSTree<SomeType>::InsertItem(SomeType item){
    Insert(rootPtr, item);
}
  
template <typename SomeType>
SomeType BSTree<SomeType>::DeleteItem(SomeType item){
    Delete(rootPtr, item);
    return item;
}

//Nothing beyond this point can be edited.

template <typename SomeType>
struct BSTreeNode{
    SomeType data;
    BSTreeNode<SomeType>* leftPtr;
    BSTreeNode<SomeType>* rightPtr;
};

template <typename SomeType>
class BSTree{
    private:
        BSTreeNode<SomeType> rootPtr;
        void Delete(BSTreeNode<SomeType>*& treePtr, SomeType& item);
        void DeleteNode(BSTreeNode<SomeType>*& treePtr);
        void Insert(BSTreeNode<SomeType>*& ptr, SomeType item);
        void Destroy(BSTreeNode<SomeType>*& ptr);
        SomeType GetPredecessor(BSTreeNode<SomeType>* treePtr) const;
    public:
        BSTree();
        ~BSTree();
        void InsertItem(SomeType item);     
        SomeType DeleteItem(SomeType item);
};

int main(){
    BSTree<int>* TestModule = new BSTree<int>;
    TestModule->InsertItem(1);
    TestModule->InsertItem(2);
    TestModule->InsertItem(4);
    TestModule->InsertItem(3);
    TestModule->DeleteItem(2);
    delete TestModule;
    TestModule = NULL;
    TestModule = new BSTree<int>;
    TestModule->InsertItem(1); //There's an extra 4 in the left pointer.
}

Solution

  • I fixed it. The problem was with Destroy; I replaced it with this.

    template <typename SomeType>
    void BSTree<SomeType>::Destroy(BSTreeNode<SomeType>*& ptr){
        if(ptr != NULL){
            Destroy(ptr->leftPtr);
            Destroy(ptr->rightPtr);
        }
        delete ptr;
    }
    

    It caused errors with a separate MakeEmpty() function, but all I had to do there was add an extra "rootPtr = NULL" line to it.