deleting node from BST

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(GPScoord1, 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;
}

Last edited on

highwayman (582)

Your just detaching entire branches without ever attaching them back to the root instead of making sure the rest of the tree stays attached.

Enoizat (1343)

You didn’t copy&paste your code correctly. The row
class BinaryTree {
is missing.

Are you sure about this line (231)?
if (root == NULL) return *root;

If ‘root’ is pointing to ‘NULL’, than return the content of ‘NULL’?

jonnin (11436)

you have to reinsert all the children if you actually delete the node.
if you mark the node as deleted instead, you don't need to do that much. There are advantages to either way.

darego (52)

I changed some code around and now the deleteCity by CityName string works fine, although deleteCity by coordinates doesn't delete the matching node. Can anyone see why?

darego (52)

I just noticed that if i run the deleteNode(19.0, 70.95) with the deleteNode("London") function then they both work fine. But if i run the coordinate function and comment out the city function then it does not work. Why is this?

Last edited on

jonnin (11436)

try everything and check everything. what happens if you run them in reverse order from what worked? What happens if you comment out coord and leave city del? London is your root node, right? Is there something special going on when you delete it? Does it work for non roots?
You can't debug it until you understand all the combos and what works and what does not. There is probably a clue in one of the other scenarios or in the root node case that will lead you to the issue.

I don't see the issue, but I did not run the thing I just looked for a couple min.

darego (52)

thanks jonnin. I have been trying for the last few hours to debug it and unfortunately can't find the problem. very annoying and it is probably something really simple that I am missing

Topic archived. No new replies allowed.

C++

Forum

deleting node from BST