Remove method in BST with 2 children, won't remove it predecessor

Question

I am trying to write a remove method for a BST. It works if there is 0 or 1 children. However, if there is 2 children the method copies the data from the predecessor (the rightmost left child) to the node-to-be-removed and then it is SUPPOSED to remove the predecessor. For some reason, the predecessor is still in the tree and doesn't get removed properly. I'm sure that this is a simple recursion bug, but I just can't figure it out! I would greatly appreciate any help, feedback and comments. Thank you.

    public boolean myRemove(Object o) {
    if (isEmpty()) {
        return false;
    }
    E data = (E)o;
    root = myRemoveHelper(root, data);
    size--;
    return true;
}
private Node<E> myRemoveHelper(Node<E> root, E data) {
    if (root.data == data) {
        return myRemoveIt(root);
    }
    else if (data.compareTo(root.data) < 0) {
        root.left = myRemoveHelper(root.left, data);
    }
    else {
        root.right = myRemoveHelper(root.right, data);
    }
    return root;
}
private Node<E> myRemoveIt(Node<E> nodeToRemove) {
    if (nodeToRemove.left == null && nodeToRemove.right == null) {
        return null;
    }
    else if (nodeToRemove.left == null && nodeToRemove.right != null) {
        return nodeToRemove.right;
    }
    else if (nodeToRemove.left != null && nodeToRemove.right == null) {
        return nodeToRemove.left;
    }
    else {
        Node<E> temp = nodeToRemove.right;
        while (temp.left != null) {
            temp = temp.left;
        }
        nodeToRemove.data = temp.data;

        //does not remove the duplicate! :(
        nodeToRemove.left = myRemoveHelper(temp, temp.data);
        return nodeToRemove;
    }
}

Answer 1

In the question you said you take the the rightmost left child but in the myRemoveIt you goes to leftmost right child in:

Node<E> temp = nodeToRemove.right;
while (temp.left != null) {
    temp = temp.left;
}

But after you assign to left: nodeToRemove.left = myRemoveHelper(temp, temp.data);.

You need to change that to:

nodeToRemove.right = myRemoveHelper(nodeToRemove.right, temp.data);

As now you sure the temp.data is on leaf (or at least we know he missing left side) and the new root you send to myRemoveHelper is the right side one as the new data is already been set.