public class BinarySearchTree$>\{$

private BinaryNode root;

public BinarySearchTree$()\{$

root $=$ null;

$\}$

public void insert$($AnyType x$)\{$

root $=$ insert$($x$,$ root$)$;

$\}$

public void remove$($AnyType x$)\{$

root $=$ remove$($x$,$ root$)$;

$\}$

public AnyType findMin$()$ throws UnderflowException $\{$

if $($isEmpty$())\{$

throw new UnderflowException$()$;

$\}$

return findMin$($root$).$element;

$\}$

public AnyType findMax$()$ throws UnderflowException $\{$

if $($isEmpty$())\{$

throw new UnderflowException$()$;

$\}$

return findMax$($root$).$element;

$\}$

public boolean contains$($AnyType x$)\{$

return contains$($x$,$ root$)$;

$\}$

public void makeEmpty$()\{$

root $=$ null;

$\}$

public boolean isEmpty$()\{$

return root $==$ null;

$\}$

public void printTree$()\{$

if $($isEmpty$())\{$

System.out.println$("$Empty tree"$)$;

$\}$ else $\{$

printTree$($root$)$;

$\}$

$\}$

private BinaryNode insert$($AnyType x$,$ BinaryNode t$)\{$

if $($t $==$ null$)\{$

return new BinaryNodex$,$ null, null$)$;

$\}$

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

if $($compareResult $<mtext></mtext><mn>0</mn><mi>)</mi><mtext></mtext><mi>\{</mi>$

t$.$left $=$ insert$($x$,$ t$.$left$)$;

$\}$ else if $($compareResult $>0)\{$

t$.$right $=$ insert$($x$,$ t$.$right$)$;

$\}$

return t;

$\}$

private BinaryNode remove$($AnyType x$,$ BinaryNode t$)\{$

if $($t $==$ null$)\{$

return t;

$\}$

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

if $($compareResult $<mtext></mtext><mn>0</mn><mi>)</mi><mtext></mtext><mi>\{</mi>$

t$.$left $=$ remove$($x$,$ t$.$left$)$;

$\}$ else if $($compareResult $>0)\{$

t$.$right $=$ remove$($x$,$ t$.$right$)$;

$\}$ else if $($t$.$left $!=$ null && t$.$right $!=$ null$)\{$

t$.$element $=$ findMin$($t$.$right$).$element;

t$.$right $=$ remove$($t$.$element, t$.$right$)$;

$\}$ else $\{$

t $=($t$.$left $!=$ null$)?$ t$.$left : t$.$right;

$\}$

return t;

$\}$

private BinaryNode findMin$($BinaryNode t$)\{$

while $($t $!=$ null && t$.$left $!=$ null$)\{$

t $=$ t$.$left;

$\}$

return t;

$\}$

private BinaryNode findMax$($BinaryNode t$)\{$

while $($t $!=$ null && t$.$right $!=$ null$)\{$

t $=$ t$.$right;

$\}$

return t;

$\}$

private boolean contains$($AnyType x$,$ BinaryNode t$)\{$

if $($t $==$ null$)\{$

return false;

$\}$

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

if $($compareResult $<mtext></mtext><mn>0</mn><mi>)</mi><mtext></mtext><mi>\{</mi>$

return contains$($x$,$ t$.$left$)$;

$\}$ else if $($compareResult $>0)\{$

return contains$($x$,$ t$.$right$)$;

$\}$ else $\{$

return true;

$\}$

$\}$

private void printTree$($BinaryNode t$)\{$

if $($t $!=$ null$)\{$

printTree$($t$.$left$)$;

System.out.println$($t$.$element$)$;

printTree$($t$.$right$)$;

$\}$

$\}$

private static class BinaryNode $\{$

AnyType element;

BinaryNode left;

BinaryNode right;

BinaryNode$($AnyType theElement, BinaryNode lt$,$ BinaryNode rt$)\{$

element $=$ theElement;

left $=$ lt;

right $=$ rt;

$\}$

$\}$

$\}$