deleting node from BST not working with std::pair

Question

I have a Binary Search Tree which is made up of Nodes containing City objects. I am trying to implement deleteCity(string cityName) and deleteCity(double GPScoord1, double GPScoord2) functions which delete the City Node which matches either the city string or 2 GPS double coordinates.

Currently the deleteCity by CityName string works fine, although deleteCity by coordinates doesn't delete the matching node. Can anyone see why?

using namespace std;
#include <utility> 
#include <iostream>

class City
{
    //friend class TreeNode;
    friend class BinaryTree;
private:
    string name;
    pair<double, double> cityCoords;
    int population;
    double tempAvg;
public:
    City(string, pair<double, double>, int, double);

    string getName();
    pair<double, double> getCityCoords();
    int getPopulation();
    double getTempAvg();

    friend ostream& operator<<(ostream&, City& c);
};

City::City(string n, pair<double, double> coords, int pop, double temp)
{
    name = n;
    cityCoords = coords;
    population = pop;
    tempAvg = temp;
}

string City::getName()
{
    return name;
}

pair<double, double> City::getCityCoords()
{
    return cityCoords;
}

int City::getPopulation()
{
    return population;
}

double City::getTempAvg()
{
    return tempAvg;
}

ostream& operator<<(ostream& out, City& c)
{
    out << "City: " << c.getName() << "\nCoordinates: " << c.getCityCoords().first 
        << ", " << c.getCityCoords().second << "\nPopulation: " 
        << c.getPopulation() << "\nAverage Yearly Temp: " << c.getTempAvg() << "\n";
    return out;
}

class TreeNode
{
    friend class BinaryTree;
    //is leaf
private:
    City city;
    TreeNode* left, * right;
    TreeNode(City *theCity);
public:
    bool isLeaf();
    City getCity();
};

TreeNode::TreeNode(City *theCity) : city(*theCity), left(nullptr), right(nullptr)
{
}

City TreeNode::getCity()
{
    return city;
}

class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();
    void add(City *city);
    int height();
    TreeNode minValue();
    void printTreeAscending() const;
    void deleteNode(string name);
    void deleteNode(double lat, double lon);

private:
    static void add(TreeNode* toAdd, City *city);
    static int height(TreeNode* root);
    static TreeNode minValue(TreeNode* node);
    static void printTreeAscending(TreeNode* root);
    TreeNode* minValueNode(TreeNode* node);
    TreeNode* deleteNode(TreeNode* node, string name);
    TreeNode* deleteNode(TreeNode*& node, pair<double, double>coords);
    TreeNode* rootPtr;
};

BinaryTree::BinaryTree() : rootPtr(nullptr)
{
}

BinaryTree::~BinaryTree()
{
    delete rootPtr;
}

void BinaryTree::add(City *city)
{
    if (rootPtr)
    {
        add(rootPtr, city);
    }
    else
    {
        rootPtr = new TreeNode(city);
    }
}

void BinaryTree::add(TreeNode* toAdd, City *city)
{
    if (city->getName() < toAdd->city.getName()) 
    {
        if (toAdd->left)
        {
            add(toAdd->left, city);
        }
        else
        {
            toAdd->left = new TreeNode(city);
        }
    }
    else {
        if (toAdd->right) {
            add(toAdd->right, city);
        }
        else {
            toAdd->right = new TreeNode(city);
        }
    }

}

int BinaryTree::height()
{
    return height(rootPtr);
}

//as per spec, returns -1 if null tree, 0 if only 1 node, 
// and 1 if there is 2 levels of nodes etc. 
int BinaryTree::height(TreeNode* node)
{
    if (!node)
    {
        return -1;
    }
    else
    {
        int leftSide = height(node->left);
        int rightSide = height(node->right);

        if (leftSide > rightSide)
        {
            return(leftSide + 1);
        }
        else
        {
            return (rightSide + 1);
        }
    }

}

TreeNode BinaryTree::minValue()
{
    return minValue(rootPtr);
}

TreeNode BinaryTree::minValue(TreeNode* node)
{
    if (node->left == nullptr) {
        return *node;
    }
    minValue(node->left);
}

void BinaryTree::printTreeAscending() const
{
    printTreeAscending(rootPtr);
    std::cout << "\n";
}

//uses In-order traversal **
//got some help on cpp forums
void BinaryTree::printTreeAscending(TreeNode* root)
{
    if (root)
    {
        printTreeAscending(root->left);
        (root->left && root->right);
        cout << root->city << "\n";
        printTreeAscending(root->right);
    }
}

bool isLeaf()
{
    if (left == nullptr && right == nullptr)
    {
        return true;
    }
    else
        return false;
}

TreeNode* BinaryTree::minValueNode(TreeNode* node)
{
    TreeNode* current = node;

    /* loop down to find the leftmost leaf */
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

//Delete City Node by City Name
void BinaryTree::deleteNode(string name) {
    deleteNode(rootPtr, name);
}

//Method found below at https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
TreeNode* BinaryTree::deleteNode(TreeNode* node, string name)
{
    if (node == NULL) return node;

    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    if (name < node->city.name)
        node->left = deleteNode(node->left, name);

    // If the key to be deleted is greater than the node's key, 
    // then it lies in right subtree 
    else if (name > node->city.name)
        node->right = deleteNode(node->right, name);

    // if key is same as node's key, then This is the node 
    // to be deleted 
    else
    {
        // node with only one child or no child 
        if (node->left == NULL)
        {
            TreeNode* temp = node->right;
            free(node);
            return temp;
        }
        else if (node->right == NULL)
        {
            TreeNode* temp = node->left;
            free(node);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        TreeNode* temp = minValueNode(node->right);

        // Copy the inorder successor's content to this node 
        node->city = temp->city;

        // Delete the inorder successor 
        node->right = deleteNode(node->right, temp->city.name);
    }
    return node;
}

//delete City Node by City Coordinates
void BinaryTree::deleteNode(double lat, double lon) {
    deleteNode(rootPtr, pair<double, double>(lat, lon));
}

//Method found below at https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
TreeNode* BinaryTree::deleteNode(TreeNode*& node, pair<double, double> coordinates)
{
    if (node == NULL) return node;

    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    if (coordinates < node->city.cityCoords)
        node->left = deleteNode(node->left, coordinates);

    // If the key to be deleted is greater than the node's key, 
    // then it lies in right subtree 
    else if (coordinates > node->city.cityCoords)
        node->right = deleteNode(node->right, coordinates);

    // if key is same as node's key, then This is the node 
    // to be deleted 
    else
    {
        // node with only one child or no child 
        if (node->left == NULL)
        {
            TreeNode* temp = node->right;
            free(node);
            return temp;
        }
        else if (node->right == NULL)
        {
            TreeNode* temp = node->left;
            free(node);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        TreeNode* temp = minValueNode(node->right);

        // Copy the inorder successor's content to this node 
        node->city = temp->city;

        // Delete the inorder successor 
        node->right = deleteNode(node->right, temp->city.cityCoords);
    }
    return node;
}

int main()
{
    City london = City("London", pair<double, double> (10.0, 40.9), 900000, 5.0);
    City dublin = City("Dublin", pair<double, double>(19.0, 70.95), 20000, 4.5);
    City madrid = City("Madrid", pair<double, double>(80.8, 100.2), 2131200, 21.0);
    City paris = City("Paris", pair<double, double>(20.6, 164.1), 804400, 11.0);
    City lisbon = City("Lisbon", pair<double, double>(49.2, 70.9), 76000, 20.0);

    BinaryTree* tree = new BinaryTree();

    City* londonPtr = &london;
    City* dublinPtr = &dublin;
    City* madridPtr = &madrid;
    City* parisPtr = &paris;
    City* lisbonPtr = &lisbon;

    tree->add(londonPtr);
    tree->add(dublinPtr);
    tree->add(madridPtr);
    tree->add(parisPtr);
    tree->add(lisbonPtr);

    cout << "Tree Height: " << tree->height() << "\n\n";

    //tree->deleteNode("London");
    tree->deleteNode(19.0, 70.95);
    tree->printTreeAscending();
    return 0;
}

Answer 1

Your add function is adding Nodes to the BST according to the name as a key.

That's how you are searching for the Node to delete, when provided a name.

However, when provided co-ordinates, you are searching by using cityCoords as a key. That's not possible. You'll need to search all branches to find the Node to delete.

This is where the issue comes from. The comment is wrong. The code that follows it is wrong as well, although it agrees with the comment.

// If the key to be deleted is smaller than the root's key, 
// then it lies in left subtree 
    if (coordinates < node->city.cityCoords)
        node->left = deleteNode(node->left, coordinates);