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

Do your findMin(...) method iteratively instead of recursively. — But I'm Not A Wrapper Class
@CyberneticTwerkGuruOrc That has no connection to the problem, and I suspect it will be optimized by most compilers anyways because this is tail recursion. I find the recursive solution more readable in this case. — amit
@amit Obviously it's not connected to the problem. That's why I posted it as a comment instead of an answer. Even if the compiler takes care of it in this case, OP should probably learn to do most methods iteratively over recursively (unless studying recursion). — But I'm Not A Wrapper Class

But I'm Not A Wrapper Class But I'm Not A Wrapper Class · Accepted Answer · 2014-04-18T20:44:21

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.

Delete from Binary Search Tree in Java

2 Answers