deleting node from Binary Search Tree not working

[darego]

I have a BST which is made up of Nodes containing City objects. I am trying to implement a deleteCity(double GPScoord1, double GPScoord2) function which deletes the City Node which matches the 2 lat and lon values passed in.

Currently this function always seems to delete the final node in the BST (Paris), once I pass in any coordinates which match any City e.g. if I pass in `10.0, 40.9` or `19.0, 70.95` or `80.8, 100.2` or ` 49.2, 70.9` the node relating to "Paris" is always deleted. If I pass coordinates in which do not match any city then no node is deleted. When I run the following code with `tree->deletion(80.8, 100.2)`, this should delete the node relating to "Madrid". Instead it deletes the node relating to "Paris".

Can anyone see why this is happening?

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

  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() << " | Coordinates: " << c.getCityCoords().first << ", " << c.getCityCoords().second << " | Population: " 
		<< c.getPopulation() << " | Average Yearly Temp: " << c.getTempAvg();
	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 deletion(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* rootPtr;
	TreeNode* deletion(TreeNode* root, pair<double, double> coordinates);
	void deleteDeepest(TreeNode* root, TreeNode* d_node);
};

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

}

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


/* function to delete the given deepest node
(d_node) in binary tree */
void BinaryTree::deleteDeepest(TreeNode* root,
	TreeNode* d_node)
{
	queue<TreeNode*> q;
	q.push(root);

	// Do level order traversal until last node 
	TreeNode* temp;
	while (!q.empty()) {
		temp = q.front();
		q.pop();
		if (temp->city.cityCoords == d_node->city.cityCoords) {
			temp = NULL;
			delete (d_node);
			return;
		}
		if (temp->right) {
			if (temp->right->city.cityCoords == d_node->city.cityCoords) {
				temp->right = NULL;
				delete (d_node);
				return;
			}
			else
				q.push(temp->right);
		}

		if (temp->left) {
			if (temp->left->city.cityCoords == d_node->city.cityCoords) {
				temp->left = NULL;
				delete (d_node);
				return;
			}
			else
				q.push(temp->left);
		}
	}
}

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

/* function to delete element in binary tree */
TreeNode* BinaryTree::deletion(TreeNode* root, pair<double, double> coordinates)
{
	if (root == NULL)
		return NULL;

	if (root->left == NULL && root->right == NULL) {
		if (root->city.cityCoords == coordinates)
			return NULL;
		else
			return root;
	}

	queue<TreeNode*> q;
	q.push(root);

	TreeNode* temp = nullptr;
	TreeNode* key_node = nullptr;

	// Do level order traversal to find deepest 
	// node(temp) and node to be deleted (key_node) 
	while (!q.empty()) {
		temp = q.front();
		q.pop();

		if (temp->city.cityCoords == coordinates)
			key_node = temp;

		if (temp->left)
			q.push(temp->left);

		if (temp->right)
			q.push(temp->right);
	}

	if (key_node != NULL) {

		pair<double, double> x = temp->city.cityCoords;
		deleteDeepest(root, temp);
		key_node->city.cityCoords = x;
	}
	return root;
}

int main()
{
        BinaryTree* tree = new BinaryTree();

	tree->add(new City("London", pair<double, double>(10.0, 40.9), 900000, 5.0));
	tree->add(new City("Dublin", pair<double, double>(19.0, 70.95), 20000, 4.5));
	tree->add(new City("Madrid", pair<double, double>(80.8, 100.2), 2131200, 21.0));
	tree->add(new City("Paris", pair<double, double>(20.6, 164.1), 804400, 11.0));
	tree->add(new City("Lisbon", pair<double, double>(49.2, 70.9), 76000, 20.0));

	tree->deletion(80.8, 100.2);
	tree->printTreeAscending();
	return 0;
}

[coder777]

On line 256 you pass temp to deleteDeepest(...) which is in fact the deepest but not the found key_node. You just overwrite the cityCoords of the found node.

Honestly I don't know what all this 'Deepest' is good for. This way you cannot delete an arbitrary node according to its data.

[darego]

It was the only example code I could find to delete from a BST that traversed the whole tree, all of the other examples I see use if key to be deleted is smaller than the roots key, then it lies in left subtree and if key to be deleted is greater than the roots key then it lies in right subtree. This won't work for me because my BST is sorted by City Name and not coordinates, so I need to traverse the full tree to find the City matching the coordinates to delete.

The below code is an example of this. Is there any easy way to make this code traverse the whole BST? instead of checking if coordinates is < or > than note->city.coords?

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 (node == nullptr)
		return node;

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

I tried the following.. but when I run my code with this function I get a read access violation root was 0xDDDDDDD, on the printTreeAscending function. So there is something wrong with my implementation

TreeNode* BinaryTree::deleteNode(TreeNode* node, pair<double, double> coordinates)
{
	if (!node)
		return node;

	deleteNode(node->left, coordinates);
	(node->left && node->right);


	// if key is same as node's key, then This is the node 
	// to be deleted 
	if (node->city.cityCoords == coordinates)
	{
		// 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);

	}

	deleteNode(node->right, coordinates);
	
	return node;
}

[coder777]

Actually the simplest way would be to store all nodes except for the one you want to delete into the queue, like you already do.

Set rootPtr = nullptr; and then use add(...) to add all remaining cities back to the tree.

[darego]

Do you know of any code examples using a queue I can look at that? I am having a hard time getting this to work correctly