Remove recursively from a binary search tree

This is homework; please don't just give me code

I have two methods: remove(T data) and removeRec(Node<T> node, T data).

In its current state, it seems my code only removes the root node of the BST.

@Override
public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    if (root == null) {
        throw new java.util.NoSuchElementException("BST is empty");
    } else {
        size--;
        BSTNode<T> dummy = new BSTNode<T>(null);
        return removeRec(root, data, dummy).getData(); //This is probably wrong too
    }
}

/**
 * Helper method to recursively search for, and remove the BSTNode with
 * the given data in it
 * @param  node is the node we're currently at
 * @param  data is the data we're looking for
 * @param  temp I have no idea why
 * @return node that was removed
 */
private BSTNode<T> removeRec(BSTNode<T> node, T data, BSTNode<T> temp) {
    if (compare(data, node.getData()) < 0) {
        temp.setLeft(removeRec(node.getLeft(), data, temp));
    } else if (compare(data, node.getData()) > 0) {
        temp.setRight(removeRec(node.getRight(), data, temp));
    } else if (node.getLeft() != null && node.getRight() != null) {
        temp.setData(findMin(node.getRight()).getData());
        temp.setRight(removeRec(node.getRight(), data, temp));
    } else {
        if (node.getLeft() != null) {
            temp = node.getLeft();
        } else {
            temp = node.getRight();
        }
    }
    return temp;
}

private int compare(T a, T b) {
    return a.compareTo(b);
}

My instructor has told me (as a hint) that I should see what passing in a third argument into the method, in this case, BSTNode<T> temp. I don't understand how that helps though, or how to utilize it. I don't see how using a third argument helps; and I can't find anything online as to why you'd do this either.

There are three main possibilities when you try to remove data from your Binary Search Tree:

data is less than the current node value: Call remove on the left subtree or throw a NoSuchElementException if it is null.
data is greater than the current node value: Call remove on the right subtree or throw a NoSuchElementException if it is null.
data is equal to the current node value.

1 and 2 are pretty straightforward, but 3 has four more cases to consider:

3.1. current node is a leaf: Both left and right subtrees are null. Just replace the reference to the current node in its parent by null.

3.2. current node has only the left child: You need to make the parent of the current node point to the left subtree, thus removing the current point. To do this, you can implement a function that will check if the current point was on the left or right subtree of the parent and replace it accordingly. Calling it would look like this:

replaceNodeInParent(node, node.getLeft(), parent);

3.3. current node has only the right child: Similar to 3.4, but using getRight() instead of getLeft().

3.4. current node has both the left and right children: You should maintain the property of the BST that all nodes on the left are less than the current node and all nodes on the right are greater than the current node. To do so, you should find the smallest value on the right, copy it to the current node, and delete it from the right subtree. Something like this:

BSTNode<T> successor = findMin(node.getRight());
node.setData(successor.getData());
removeRec(node.getRight(), successor.getData(), node);

It looks like your BSTNode doesn't hold a reference to the parent node. If so, I believe that's what the third argument for removeRec should be. You will need a reference to the parent every time you replace the current node, so you can set the parent left or right subtree as needed.

For further reading, you can check this article on Binary Search Trees from Wikipedia.