package binarysearchtree;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )    --> Insert x
// void remove( x )    --> Remove x
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( )    --> Remove all items
// void printTree( )    --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author
*/

import java.lang.Exception;
import java.util.NoSuchElementException;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
   root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
   root = insert( x, root );
}

/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
   root = remove( x, root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
   if( isEmpty( ) )
         throw new UnderflowException( );
   return findMin( root ).element;
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
   if( isEmpty( ) )
         throw new UnderflowException( );
   return findMax( root ).element;
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
   return contains( x, root );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
   root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
   return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
   if( isEmpty( ) )
         System.out.println( "Empty tree" );
   else
         printTree( root );
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
   if( t == null )
         return new BinaryNode<>( x, null, null );

   if( t.left == null )
   {
         t.left = new BinaryNode<>( x, null, null );
         return t.left;
   }

   else if( t.right == null )
   {
         t.right = new BinaryNode<>( x, null, null );
         return t.right;
   }
   else
         ;

   int compareResult = x.compareTo( t.element );
   System.out.println(compareResult);
   if( compareResult < 0 )
         t.left = insert( x, t.left );
   else if( compareResult > 0 )
         t.right = insert( x, t.right );
   else
         ; // Duplicate; do nothing
   return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
   if( t == null )
         return t; // Item not found; do nothing

   int compareResult = x.compareTo( t.element );

   if( compareResult < 0 )
         t.left = remove( x, t.left );
   else if( compareResult > 0 )
         t.right = remove( x, t.right );
   else if( t.left != null && t.right != null ) // Two children
   {
         t.element = findMin( t.right ).element;
         t.right = remove( t.element, t.right );
   }
   else
         t = ( t.left != null ) ? t.left : t.right;
   return t;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
   if( t == null )
         return null;
   else if( t.left == null )
         return t;
   return findMin( t.left );
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
   if( t != null )
         while( t.right != null )
            t = t.right;

   return t;
}

Exercise #1 - Fraction Problem (10pts) Define a class called Fract...