Ok so I thought it was fixed, but I'm getting totally inconsistent results. I rewrote it kind of from scratch to start fresh and here are my results. I get no errors, no crashing, it just doesn't remove them. It just totally messes up the tree and gives me a ton more leaves, and mixes everything up. Not sure where else to go
template <class T>
void BST<T>::remove(struct Node<T>*& root, const T& x)
{
Node<T>* ptr = root;
bool found = false;
Node<T>* parent;
while (ptr != NULL && !found)
{
if (x < ptr->data)
{
parent = ptr;
ptr = ptr->left;
}
else if (x > ptr->data)
{
parent = ptr;
ptr = ptr->right;
}
else
found = true;
}
if (found == false)
return;
else
{
if(ptr->left != NULL && ptr->right != NULL)
{
Node<T>* inOrderPtr = ptr->left;
parent = ptr;
while (inOrderPtr->right != NULL)
{
parent = inOrderPtr;
inOrderPtr = inOrderPtr->right;
}
ptr->data = inOrderPtr->data;
ptr = inOrderPtr;
}
Node<T>* subPtr = ptr->left;
if (subPtr == NULL)
subPtr = ptr->right;
else if (parent->left == ptr)
parent->left = subPtr;
else
parent->right = subPtr;
delete ptr;
}