Hmm. What exactly is case 4?
It seems these lines are likely the culprit:
TreeNode n = findParent(largestValue.getKey(), this.root);
n.right = null;
How can you be sure that n's right side must be set null? What if n is the same as nodeToRemove? That is, the largest value in the left subtree is in the node which is nodeToRemove.left?
Maybe you need an additional case to handle this.