Delete from Binary Search Tree in Java

Question

I can't find what is wrong with my deletion algorithm. When I run my delete method on the root of the BST, it will replace the root with the value of the minimum of the right subtree, but it is not deleting the node thereafter.

public void delete(BinaryTreeNode node, int x){
     if (node==null)
         return;
     else if (x<node.getKey())
         delete(node.getLeftChild(),x);
     else if (x>node.getKey())
         delete(node.getRightChild(),x);
     else{
         if (node.getLeftChild()==null)
             node = node.getRightChild();
         else if (node.getRightChild()==null)
             node = node.getLeftChild();
         else{
             BinaryTreeNode temp = findMin(node.getRightChild());
             System.out.println(temp.getKey() + "   " + node.getKey());
             node.setKey(temp.getKey());
             System.out.println(temp.getKey() + "   " + node.getKey());
             delete(node.getRightChild(), node.getKey());
         }
     }
 }

and my findMin() method:

public BinaryTreeNode findMin(BinaryTreeNode node){  
     if (node.getLeftChild()==null)
         return node;
     else
         return findMin(node.getLeftChild());
}

For a BST containing all integers 1-9 with a root of 4, my output for inorderPrint() yields

1,2,3,5,5,6,7,8,9 

instead of

1,2,3,5,6,7,8,9

Answer 1

When you are setting node = node.getLeftChild(); (or symetrically node = node.getRightChild(); you are changing the value of the local variable node, and not the reference to this node from the father.

You are missing something like:node.father.left = ....(or node.father.right = ...).
You should change the values in the tree itself, and not only the references you hold in the method.

Answer 2

Update your deleted-node's parent's pointer with the correct node. You need to get rid of any traces of the deleted node. Have a temporary node to keep track of the parent node, so this is easier to do once you find the node to delete.