Removing a binary search tree (Inred Pred method) C ++

Question

Ok, so I thought this was fixed, but I get completely inconsistent results. I rewrote it from scratch to start a new one, and here are my results. I get no errors, no crashes, it just doesn't delete them. It just spoils the tree completely and gives me a ton of more leaves and mixes everything. 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; } 

Answer 1

Are each T found in a tree unique? It looks like they are from your code ...

Seems like this should work:

Otherwise, deleting the root of the node:

 Node<T> *tmp_r = root->left; Node<T> *parent = root; while (tmp_r->right != NULL) { parent = tmp_r; tmp_r = tmp_r->right; } Node<T> *tmp_l = tmp_r; while (tmp_l->left != NULL) tmp_l = tmp_l->left; tmp_l->left = root->left; tmp_r->right = root->right; parent->right = NULL; parent = root; root = tmp_r; delete parent; 

Answer 2

What actually happened was that the search could be canceled, so in fact it just kept going right, but the data was actually not true, and so it hit the wall.

 if (root->data < x) remove(root->left, x); else remove(root->right, x); 

should be

 if(x < root->data) remove(root->left, x); else remove(root->right, x); 

Answer 3

You should not call remove() recursively in the third case (where your comment is "not sure if this is correct"). In the case where the node has two children for deletion, what you want to do is find the rightmost child of the left child (as you do, the resulting node is stored in parent ). This node does not have the right of a child - make it so that its right child is the correct child node to delete. Then just change the root variable to its left child; there is no need to change the data member in any nodes or call remove recursively.

In the images:

  Before:
          r <- root points here
        / \
       / \
      ab
     / \ / \
    xcyy
       / \
      xd
         /
        x

 After:
       a <- root points here
      / \
     xc
        / \
       xd
          / \
         xb
            / \
           yy