CODEWITHSUNDEEP
c++data-structures
satazero
satazero

Reputation: 37

Strange Node Deletion in Binary Search Tree

I'm writing out a BST that holds some data, and I'm trying to implement the function for removing a single element from the BST.

Currently, my recursiveDelete() function looks as follows, and it works! Depending on your definition of works. It takes some other nodes along with it.

template <typename ItemType, typename KeyType>
BNode<ItemType>* BinarySearchTree<ItemType, KeyType>::recDeleteNode(KeyType key, BNode<ItemType> *subtree)
{
    if (subtree == nullptr) 
    {
        return subtree;
    }
    else if (subtree->getItem() > key)
    {
        subtree->setLeft(recDeleteNode(key, subtree->getLeft()));
    }
    else if (subtree->getItem() < key)
    {
        subtree->setRight(recDeleteNode(key, subtree->getRight()));
    }
    else 
    {
        if (subtree->getLeft() == nullptr && subtree->getRight() == nullptr)
        {
            delete subtree;
            subtree = nullptr;
        }
        else if (subtree->getLeft() == nullptr)
        {
            BNode<ItemType> *temp = subtree;
            subtree = subtree->getRight();
            delete temp;
        }
        else if (subtree->getRight() == nullptr)
        {
            BNode<ItemType> *temp = subtree;
            subtree = subtree->getRight();
            delete temp;
        }
        else
        {
            BNode<ItemType> *temp = minValueNode(subtree->getRight());
            temp->setLeft(subtree->getLeft());
            temp = subtree;
            subtree = subtree->getRight();
            delete temp;
        }
    }

    return subtree;
}

The ItemType comparison operators are overloaded, since the key is defined inside the actual data that the Node points to.

I've been staring at this for a while, but I cannot see what would cause it to pull out another nodes along with it.

Upvotes: 1

Views: 35

Answers (1)

David Schwartz
David Schwartz

Reputation: 182829

    else if (subtree->getRight() == nullptr)
    {
        BNode<ItemType> *temp = subtree;
        subtree = subtree->getRight(); // this is nullptr
        delete temp;
    }

That getRight should be getLeft.

Upvotes: 4

Related Questions