Binary Search Tree - Removal results in incorrect tree

Question

I'm trying to learn data structures myself and I'm struggling to understand how the remove method should work for a Binary Search Tree. I'm following the example from Data Structures and Algorithms - Barnett & Del Tongo textbook:

I've got most of it working, however this section of my code is resulting in the tree being incorrect:

        //Case 4
        TreeNode largestValue = nodeToRemove.left;

        while (largestValue.right != null) {
            //Find the largest value in the left subtree of nodeToRemove
            largestValue = largestValue.right;
        }
        TreeNode n = findParent(largestValue.getKey(), this.root);
        n.right = null;
        nodeToRemove.key = largestValue.getKey();

If you can help me fix it or recommend a better resource that will help me construct this method correctly, that would be great.

Answer 1

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.