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;

}

Explanation / Answer

public boolean delete(final T val) { //the node to be deleted Node target = null; //to keep track of parent node Node parent = null; //variable node reference Node node = root; while (node != null) { if (val.compareTo( node.getValue() ) == 0) //eureka! { target = node; break; } else if (val.compareTo( node.getValue() ) > 0) //target greater, so go right { parent = node; node = node.getRight(); } else //target less, so go left { parent = node; node = node.getLeft(); } } if (target == null) { //target not found return false; } boolean isLeft = (target == parent.getLeft() ); if (target == root) //the node that's baleeting is in fact the root node { //get last house on the left on the right! //it becomes the new root node = getLastHouseOnTheLeft( parent.getRight() ); if (node != null) { node.setLeft( parent.getLeft() ); node.setRight( parent.getRight() ); root = node; } } else if ( target.isLeaf() ) { if (isLeft) { parent.setLeft(null); } else { parent.setRight(null); } } else if (target.getLeft() != null && target.getRight() != null) //two children, some shuffling { if (isLeft) { parent.setLeft( target.getRight() ); parent.getLeft().setLeft( target.getLeft() ); } else { parent.setRight( target.getRight() ); parent.getRight().setLeft( target.getLeft() ); } } else //one child is simpler { if (target.getLeft() == null) { if (isLeft) { parent.setLeft( target.getLeft() ); } else { parent.setRight( target.getLeft() ); } } else { if (isLeft) { parent.setLeft( target.getRight() ); } else { parent.setRight( target.getRight() ); } } } return true; //baleeted } public Node getNode(T v) { //null guard if (v == null) { return null; } Node node = root; int comp; while (root != null) { comp = node.getValue().compareTo(v); if (comp == 0) { return node; } if (comp > 0) { node = node.getLeft(); } else { node = node.getRight(); } } return node; }

Navigate

I am trying to identify the functional group present based on the IR Spectrum. C

I am trying to implement The Sieve of Eratosthenes to output: Enter the limit: 1

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

I am trying to implement BinarySearchTree remove() method in a recursive way. I

Question

Explanation / Answer

Related Questions

Navigate