class BasicDictionary
{
   class TreeNode
   {
     protected String data;
     protected TreeNode lessChild;
     protected TreeNode greaterChild;

     TreeNode(String data)
     {
        this.data = data;
        this.lessChild = null;
        this.greaterChild = null;
     }
     
     public String toString()
     {
       String ret = this.data.toString();
       ret += " [";
       if (this.lessChild != null)
       {
         ret += lessChild.toString();
       }
       ret += "] [";
       if (this.greaterChild != null)
       {
         ret += greaterChild.toString();
       }
       ret += "]";
       return ret;
     }
   }

   protected TreeNode root;   // Reference to the root of the tree

   BasicDictionary()
   {
     this.root = null;
   }

   public void insert(String data)
   {
     TreeNode n = new TreeNode(data);
     if (this.root == null )
     {
       this.root = n;
     }
     else
     {
       TreeNode current = this.root;
       TreeNode prev = null;
       while (current != null)
       {
         prev = current;
         if (data.compareTo(current.data) < 0)
         {
           current = current.lessChild;
           if (current == null)
           {
             prev.lessChild = n;
           }
         }
         else 
         {
           current = current.greaterChild;
           if (current == null)
           {
             prev.greaterChild = n;
           }
         }
       }
     }
   }
   
   public String toString()
   {
     if (this.root == null)
     {
       return "Empty Dictionary";
     }
     String ret = this.root.toString();
     
     return ret;
   }
   
   public static void main( String[] args )
   {
     BasicDictionary dict = new BasicDictionary();
     dict.insert( "Hello" );
     dict.insert( "SPAM" );
     dict.insert( "Abcd" );
     dict.insert( "Xyz" );
     System.out.println( dict );
   }
}

class Dictionary extends BasicDictionary
{
  public void delete( String s )
  {
    TreeNode current = root;
    TreeNode prev = null;
    while (current != null && !current.data.equals( s ))
    {
      prev = current;
      // find the node to delete
      if (s.compareTo(current.data) < 0)
      {
        current = current.lessChild;
      }
      else
      {
        current = current.greaterChild;
      }
    }
    if (current != null)
    {
      if (current.lessChild == null && current.greaterChild == null )
      {
        replace( prev, current, null );
      }
      else if (current.lessChild == null)
      {
        replace( prev, current, current.greaterChild );
      }
      else if (current.greaterChild == null)
      {
        replace( prev, current, current.lessChild );
      }
      else
      {
        TreeNode n = getReplaceNode( current );
        if ( n != current.greaterChild )
        {
          n.greaterChild = current.greaterChild;
        }
        n.lessChild = current.lessChild;
        replace( prev, current, n );
      }
    }
  }
  
  private TreeNode getReplaceNode( TreeNode current )
  {
    TreeNode step = current.greaterChild;
    TreeNode prev = current;
    TreeNode prev2 = null;
    while ( step != null )
    {
      prev2 = prev;
      prev = step;
      step = step.lessChild;
    }
    if ( prev2 != current )
    {
      prev2.lessChild = prev.greaterChild;
    }
    return prev;
  }
  
  private void replace( TreeNode prev, TreeNode current, TreeNode replNode )
  {
    if (prev == null)
    {
      this.root = replNode;
    }
    else if ( prev.lessChild == current )
    {
      prev.lessChild = replNode;
    }
    else
    {
      prev.greaterChild = replNode;
    }
  }
  
  public static void main( String[] args )
  {
    Dictionary dict = new Dictionary();
    dict.insert( "Hello" );
    dict.insert( "SPAM" );
    dict.insert( "Abcd" );
    dict.insert( "Xyz" );
    dict.insert( "My" );
    System.out.println( dict );
    dict.delete( "Hello" );
    System.out.println( dict );

  }
}