Can't delete a Node from the Binary Search Tree

[kamilhassaan]

My header file

#include <iostream>
#include <string>

using namespace std;

class BinaryTree
{
private:
	class btNode
	{
	public:
		int key;
		btNode *left;
		btNode *right;
	};

	btNode *root;

	btNode *CreateLeaf(int _key);
	void AddLeafPrivate(int _key, btNode *btPtr);
	void printInOrderPrivate(btNode *btPtr);
	btNode *ReturnNodePrivate(int _key, btNode *btPtr);

	int FindSmallestPrivate(btNode *btPtr);
	int FindMaximumPrivate(btNode *btPtr);

	btNode *deletePrivate(btNode *btPtr, int _key);

public:
	BinaryTree();

	void AddLeaf(int _key);
	void printInOrder();
	btNode *ReturnNode(int _key);
	int FindSmallest();
	int FindMaximum();
	void deleteNode(int _key);

	~BinaryTree();
};

My function definition file. Delete function is declared is defined at the top

#include "BST.h"

void BinaryTree::deleteNode(int _key)
{
	deletePrivate(root, _key);
}

BinaryTree::btNode* BinaryTree::deletePrivate(btNode *btPtr, int _key)
{
	if (root == NULL)
	{
		return root;
	}
	else if (_key < root->key)								//Traverse to the left side if key is smaller
	{
		root->left = deletePrivate(root->left, _key);
	}
	else if (_key > root->key)								//Traverse to the right side if key is greater
	{
		root->right = deletePrivate(root->right, _key);
	}
	else													//The key has been found
	{
		//Case 1 : No child
		if ((root->left == NULL) && (root->right == NULL))
		{
			delete root;
			root = NULL;
		}
		//Case 2 : One child
		else if (root->left == NULL)
		{
			btNode *temp = root;
			root = root->right;
			delete temp;
		}
		else if (root->right == NULL)
		{
			int temp = FindSmallest();
			root->key = temp;
			root->right = deletePrivate(root->right, temp);
		}
	}

	return root;
}

BinaryTree::BinaryTree()
{
	root = NULL;
};

BinaryTree::btNode* BinaryTree::CreateLeaf(int _key)
{
	btNode *temp = new btNode;

	temp->key = _key;
	temp->left = temp->right = NULL;

	return temp;
}

void BinaryTree::AddLeaf(int _key)
{
	AddLeafPrivate(_key, root);
}

void BinaryTree::AddLeafPrivate(int _key, btNode *btPtr)
{
	if (root == NULL)
	{
		root = CreateLeaf(_key);
	}
	else if (_key < btPtr->key)		//if value is smaller
	{
		if (btPtr->left != NULL)
		{
			AddLeafPrivate(_key, btPtr->left);
		}
		else
		{
			btPtr->left = CreateLeaf(_key);
		}
	}
	else if (_key > btPtr->key)		//if value is greater
	{
		if (btPtr->right != NULL)
		{
			AddLeafPrivate(_key, btPtr->right);
		}
		else
		{
			btPtr->right = CreateLeaf(_key);
		}
	}
	else
	{
		cout << "The key " << _key << " is already present in the tree" << endl;
	}
}

void BinaryTree::printInOrder()
{
	printInOrderPrivate(root);
}

void BinaryTree::printInOrderPrivate(btNode *btPtr)
{
	if (btPtr)
	{
		if (btPtr->left != NULL)
		{
			printInOrderPrivate(btPtr->left);
		}

			cout << btPtr->key << " ";
		
		if (btPtr->right != NULL)
		{
			printInOrderPrivate(btPtr->right);
		}
	}
	else
	{
		cout << "Tree is empty" << endl;
	}
}

BinaryTree::btNode* BinaryTree::ReturnNode(int _key)
{
	return ReturnNodePrivate(_key, root);
}

BinaryTree::btNode* BinaryTree::ReturnNodePrivate(int _key, btNode *btPtr)
{
	if (btPtr != NULL)
	{
		if (btPtr->key == _key)
		{
			return btPtr;
		}
		else
		{
			if (_key < btPtr->key)
			{
				return ReturnNodePrivate(_key, btPtr->left);
			}
			else
			{
				return ReturnNodePrivate(_key, btPtr->right);
			}
		}
	}
	else
	{
		return NULL;
	}
}

int BinaryTree::FindSmallest()
{
	return FindSmallestPrivate(root);
}

int BinaryTree::FindSmallestPrivate(btNode *btPtr)
{
	if (root == NULL)
	{
		cout << "The tree is empty" << endl;
		
		return NULL;
	}
	else
	{
		if (btPtr->left != NULL)
		{
			return FindSmallestPrivate(btPtr->left);
		}
		else
		{
			return btPtr->key;
		}
	}
}

int BinaryTree::FindMaximum()
{
	return FindMaximumPrivate(root);
}

int BinaryTree::FindMaximumPrivate(btNode *btPtr)
{
	if (root == NULL)
	{
		cout << "The tree is empty" << endl;

		return NULL;
	}
	else
	{
		if (btPtr->right != NULL)
		{
			return FindMaximumPrivate(btPtr->right);
		}
		else
		{
			return btPtr->key;
		}
	}
}


BinaryTree::~BinaryTree()
{
	cout << "Destructor is called" << endl;
}

My main file

#include "BST.h"

int main()
{
	int TreeKeys[16] = { 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80 };
	
	BinaryTree myTree;

	for (int i = 0; i < 16; i++)
	{
		myTree.AddLeaf(TreeKeys[i]);
	}

	myTree.printInOrder();

	cout << endl;

	cout << myTree.FindSmallest() << endl;
	cout << myTree.FindMaximum() << endl;

	myTree.deleteNode(2);

	myTree.printInOrder();

	system("pause");
	return 0;
}

The program crashes after i try to delete a node.

[wildblue]

The node pointer being passed into the delete function is called btPtr, but the function is checking the pointer root instead of btPtr. There's infinite recursion of the function.

BinaryTree::btNode* BinaryTree::deletePrivate(btNode *btPtr, int _key)
{
	if (root == NULL)
	{
		return root;
	}
	else if (_key < root->key)								//Traverse to the left side if key is smaller
	{
		root->left = deletePrivate(root->left, _key);
	}
	else if (_key > root->key)								//Traverse to the right side if key is greater
	{
		root->right = deletePrivate(root->right, _key);
	}
	else													//The key has been found
	{
		//Case 1 : No child
		if ((root->left == NULL) && (root->right == NULL))
		{
			delete root;
			root = NULL;
		}
		//Case 2 : One child
		else if (root->left == NULL)
		{
			btNode *temp = root;
			root = root->right;
			delete temp;
		}
		else if (root->right == NULL)
		{
			int temp = FindSmallest();
			root->key = temp;
			root->right = deletePrivate(root->right, temp);
		}
	}

	return root;
}