In this problem, you will implement various algorithms operating on binary search trees. We have provided with you a standard implementation of a generic BST in BinarySearchTree. java. Note that this class is an abstract class, which means that some of its methods are not implemented. In previous assignments, you have implemented interfaces which specified methods that you needed to write. Very similarly, an abstract class is a class with some unimplemented methods (it can be thought of somewhat like an interface but with some methods actually implemented). You will need to write a BetterBST class which extends BinarySearchTree. Your BetterBST class can then be treated just like a regular BinarySearchTree, just with some additional functionality.

The methods that you will need to implement in BetterBST perform various algorithms on BST instances. For some of these methods, you may find it convenient to implement a private helper method as you did in previous assignments.

public T smallestGreaterThan(T t) - given some generic comparable value t, find the smallest value in the BST that is larger than t. For example, if a binary search tree contains the values 1, 3, and 5, and the function is called with t = 2, it should return 3.
public abstract class BinarySearchTree>
{
// implement these!
abstract int height();
abstract T imbalance();
abstract BinarySearchTree mirror();
abstract T smallestGreaterThan(T t);
abstract void prettyPrint();

// stripped down from https://users. cs. fiu. edu/~weiss/dsaajava2/code/BinarySea rchTree. java
public BinarySearchTree( )
{
root = null;
}

public void insert( T x )
{
root = insert( x, root );
}

public void remove( T x )
{
root = remove( x, root );
}

public T findMin( )
{
if(root == null)
throw new NullPointerException( );
return findMin( root ).data;
}

public boolean contains( T x )
{
return contains( x, root );
}

private BinaryNode insert( T x, BinaryNode t )
{
if( t == null )
return new BinaryNode( x, null, null );

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

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;
}

private BinaryNode remove( T x, BinaryNode t )
{
if( t == null )
return t; // Item not found; do nothing

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

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. data = findMin( t. right ).data;
t. right = remove( t. data, t. right );
}
else
t = ( t. left != null ) ? t. left : t. right;
return t;
}

private BinaryNode findMin( BinaryNode t )
{
if( t == null )
return null;
else if( t. left == null )
return t;
return findMin( t. left );
}

private boolean contains( T x, BinaryNode t )
{
if( t == null )
return false;

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

if( compareResult < 0 )
return contains( x, t. left );
else if( compareResult > 0 )
return contains( x, t. right );
else
return true; // Match
}

static class BinaryNode
{

BinaryNode( T thedata )
{
this( thedata, null, null );
}

BinaryNode( T thedata, BinaryNode lt, BinaryNode rt )
{
data = thedata;
left = lt;
right = rt;
}

T data; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}

BinaryNode root;
}