DELETION FROM A BINARY TREE

// post: deletes a node with data equal to target, if present,
// preserving binary search tree property
public void delete( Comparable target )
{
  myRoot = deleteHelper( myRoot, target );
}

// pre : node points to a non-empty binary search tree
// post: deletes a node with data equal to target, if present,
// preserving binary search tree property
private TreeNode deleteHelper( TreeNode node, Comparable target )
{
  if ( node == null )
  {
    throw new NoSuchElementException();
  }
  else if ( target.compareTo( node.getValue() ) == 0 )
  {
    return deleteTargetNode( node );
  }
  else if ( target.compareTo( node.getValue() ) < 0 )
  {
    node.setLeft( deleteHelper( node.getLeft(), target ) );
    return node;
  }
  else //target.compareTo( root.getValue() ) > 0
  {
    node.setRight( deleteHelper( node.getRight(), target ) );
    return node;
  }
}

// pre : target points to node to be deleted
// post: target node is deleted preserving binary search tree property
private TreeNode deleteTargetNode( TreeNode target )
{
  if ( target.getRight() == null )
  {
    return target.getLeft();
  }
  else if ( target.getLeft() == null )
  {
    return target.getRight();
  }
  else if ( target.getLeft().getRight() == null )
  {
    target.setValue( target.getLeft().getValue() );
    target.setLeft( target.getLeft().getLeft() );
    return target;
  }
  else // left child has right child
  {
    TreeNode marker = target.getLeft();
    while ( marker.getRight().getRight() != null )
      marker = marker.getRight();

    target.setValue( marker.getRight().getValue() );
    marker.setRight( marker.getRight().getLeft() );
    return target;
  }
}

// ------------------ testDelete method - add to BSTree.java

public void testDelete( BinarySearchTree temp )
{
  int idToDelete;
  
  System.out.println( "Testing delete algorithm\n" );
  System.out.print( "Enter Id value to delete (-1 to quit) --> " );
  idToDelete = console.nextInt();

  while ( idToDelete >= 0 )
  {
    Item dNode = new Item( idToDelete, 0 );

    if ( temp.find( dNode ) == null )
      System.out.println( "Id# " + idToDelete + " No such part in stock" );
    else
    {
      temp.delete( dNode );
      System.out.println( " Id #" + idToDelete + " was deleted" );
    }
    System.out.println();
    System.out.print( "Enter Id value to delete (-1 to quit) --> " );

    idToDelete = console.nextInt();
  }
}