Error when Deleting Node from BST

Question

This genuinely has me stumped. I have a binary search tree of citys that is ordered by the city name. A city also contains the population and GPS coordinates. I want to be able to remove nodes from the tree by City name or city coordinates. I have the delete by name working fine but the GPS coordinates does not work.

When I remove a node by GPS I get a stack-overflow when I try to print the binary tree. Below is some of my code. I cannot understand how it will work fine if I delete by name but not if I delete by coordinates as I am using the same delete method.

The exact error I get is "Unhandled exception at 0x013214D6 in EXE: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00152FFC)." This occurs in my print function after I delete by coordinates but not if I delete by name.

bool BinaryTree::DeleteByName(string city)
{
    if (GetRoot() != NULL)
    {
        return (DeleteByName(GetRoot(), city));
    }
    return false;
}

TreeNode* BinaryTree::DeleteByName(TreeNode *node, string city)
{
    if (node == NULL)
    {
        return node;
    }
    else if (city < node->Data.name)
    {
        node->Left = DeleteByName(node->Left, city);
    }
    else if (city > node->Data.name)
    {
        node->Right = DeleteByName(node->Right, city);
    }
    else
    {
        if (node->Left == NULL && node->Right == NULL)
        {
            delete node;
            node = NULL;
        }
        else if (node->Left == NULL)        
        {
            TreeNode* temp = node;
            node = node->Right;
            delete temp;
        }
        else if (node->Right == NULL)
        {
            TreeNode* temp = node;
            node = node->Left;
            delete temp;
        }
        else
        {
            cout << "Else";
            TreeNode* temp = MinPtr(node->Right);
            node->Data = temp->Data;
            node->Right = DeleteByName(node->Right, temp->Data.name);
        }
    }
    return node;
}

bool BinaryTree::DeleteByCoord(pair<double, double> coords)
{
    if (GetRoot() == NULL)
    {
        return false;
    }
    else
    {
        return DeleteByCoord(GetRoot(), coords);
    }
}

bool BinaryTree::DeleteByCoord(TreeNode* node, pair<double, double> coords)
{
    bool result;

    if (node == NULL)
    {
        return false;
    }
    else
    {
        if (node->Data.coordinates.first == coords.first && node->Data.coordinates.second == coords.second)
        {
            return (DeleteByName(node, node->Data.name));           
        }

        result = DeleteByCoord(node->Left, coords);
        if (result == true)
        {
            return result;
        }

        return DeleteByCoord(node->Right, coords);
    }
}




void BinaryTree::Insert(City city)
{
    TreeNode* temp = new TreeNode(city);
    if (GetRoot() == NULL)
    {
        root = temp;
    }
    else
    {
        Insert(temp, GetRoot());
    }
}

void BinaryTree::Insert(TreeNode* toAdd, TreeNode* addHere)
{
    if (toAdd->Data < addHere->Data)
    {
        if (addHere->Left != NULL)
        {
            Insert(toAdd, addHere->Left); 
        }
        else
        {
            addHere->Left = toAdd;
        }
    }
    else if (toAdd->Data > addHere->Data)
    {
        if (addHere->Right != NULL)
        {
            Insert(toAdd, addHere->Right);
        }
        else
        {
            addHere->Right = toAdd;
        }
    }
}

void BinaryTree::InOrderTraversal(TreeNode* node)
{
    if (node != NULL)
    {
        InOrderTraversal(node->Left);
        cout << node->Data << endl;
        InOrderTraversal(node->Right);
    }
}

void BinaryTree::InOrderTraversal()
{
    InOrderTraversal(GetRoot());
}

TreeNode* BinaryTree::GetRoot()
{
    return root;
}

TreeNode* BinaryTree::MinPtr(TreeNode* node)
{
    while (node->Left != NULL)
    {
        node = node->Left;
    }   
    return node;
}

score 0 · Accepted Answer · edited May 23 '17 at 11:54

When you delete the node you also need to update parent pointer that points to deleted node. Pay attention here:

when you call DeleteByName directly it searches required node and returns NULL pointer which automatically set to parent node pointer:

else if (city < node->Data.name)
{
    node->Left = DeleteByName(node->Left, city);
}
else if (city > node->Data.name)
{
    node->Right = DeleteByName(node->Right, city);
}

but when you call DeleteByName from coordinates method you do not reset parent's Left/Right pointers:

if (node->Data.coordinates.first == coords.first && node->Data.coordinates.second == coords.second)
{
    return (DeleteByName(node, node->Data.name));           
}

in its turn as DeleteByName already receives required node, it does not perform recursive call and does not reset parent's pointers either:

else
{
    if (node->Left == NULL && node->Right == NULL)
    {
        delete node;
        node = NULL;
    }
    //... same here
}

NOTE: There are many more problems in your code. Some that strike the eye:

DeleteByName returns pointer, but DeleteByCoord returns bool, you use pointer as a boolean type in DeleteByCoord
Avoid to compare doubles directly, the comparison result can be wrong. See the question and explanation for the details.

That makes sense, so the pointer that was pointing to the node I have now deleted is pointing to nothing and is causing the error? Is the best solution to create a method to keep track of the node to be deleted and the node to be deleted parent? — crazyeyes, May 01 '17 at 23:45
@crazyeyes not to nothing I would say but to garbage, and accessing such memory is undefined behavior. Something like that. Or you can just delete the node from parent, without navigating to it. I.e. something like if ( city == node->Left->Data.name) { delete node->Left->Data; delete node->Left; node->Left = NULL; } And the same for the Right. — VeminZ, May 02 '17 at 00:19

Error when Deleting Node from BST

1 Answers1