I am trying to implement BinarySearchTree remove() method in a recursive way. I
ID: 664318 • Letter: I
Question
I am trying to implement BinarySearchTree remove() method in a recursive way.
I get the idea of it but it is very confusing to implement. plz look at the code that I have for now and fix so it works.
getSuccessor() is the successor it is implemented already .
public boolean remove(AnyType item)
{
// TODO
if(item == null)
{
throw new NullPointerException();
}
if (root == null)
{
return false;
}
removeRecursive(root, item);
if(isRemoved)
{
return true;
}
return false;
}
private boolean removeRecursive (BinarySearchNode<AnyType> current, AnyType item)
{
//if the item matches, do the remove!!
isRemoved = false;
if (contains(item))
{
//left
if (item.compareTo(current.getData())<0)
removeRecursive(current.getLeft(), item);
else if (item.compareTo(current.getData())>0)
removeRecursive(current.getRight(), item);
else
//case 3. two children
if(current.getLeft() != null & current.getRight() != null)
{
current.setData(current.getSuccessor().getData()); //replaced with the successor
current.getSuccessor().setData(null);
isRemoved = true;
}
//case 2. one child
else if(current.getLeft() != null) //has right child but no left child
{
BinarySearchNode<AnyType> trash = current;
current = current.getLeft();
trash = null;
isRemoved = true;
//current.setLeft(current.getLeft());
}
else if(current.getRight() != null)
{
BinarySearchNode<AnyType> trash = current;
current = current.getRight();
trash = null;
isRemoved = true;
}
else //case 1. no child
{
current = null;
isRemoved = true;
}
return isRemoved;
}
else
return isRemoved;
}