Error when Deleting Node from BST

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;
}

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.