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
– But I'm Not A Wrapper Class, Commented Apr 18, 2014 at 20:37
@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, Commented Apr 18, 2014 at 20:39
@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, Commented Apr 18, 2014 at 20:40

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

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.

answered Apr 18, 2014 at 20:44

But I'm Not A Wrapper Class

14.4k6 gold badges48 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

amit · Accepted Answer · 2014-04-18 20:44:59Z

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.

answered Apr 18, 2014 at 20:44

amit

179k27 gold badges245 silver badges348 bronze badges

Collectives™ on Stack Overflow

Delete from Binary Search Tree in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related