whdgns0665 whdgns0665 - 9 months ago 46
C++ Question

Binary search tree valgrind error "Invalid read of size 8"

I'm creating a recursive function for a binary search tree that removes the minimum node, which would be the leftmost node in the tree. I start at the root and traverse down from there. I'm trying to understand why I'm getting an "invalid read of size 8" error. I'm pretty sure the current node I'm at will never be NULL and I created a conditional for if the tree is empty.

void removeMinimumValue()
{
removeMinimumValue(root);
}

void removeMinimumValue(BSTNode *node)
{
if(root==NULL)
exit(1);
else if (node->leftChild==NULL)
delete node;
else
removeMinimumValue(node->leftChild);
}

Answer Source

I suppose this happens during the second removal of the minimum value? During the first removal, you delete the lowest node, but it's parent still has a reference to it (a "dangling pointer"). Next iteration, the function will try to read the deleted node.

I'd also like to add that if the lowest node has a right child, you have to add it as the left child,of it's parent node. Otherwise you're losing those nodes. You don't even have to check if this node has right children, because if it's NULL, you'd have to write NULL to the left child of the parent of the deleted node.

So change delete node; to

node->parent->leftChild = node->rightChild;
delete node;