public class BST$>$ implements BSTInterface$\{$

protected BSTNode root; $//$ reference to the root of this BST

boolean found; $//$ used by remove

public BST$()$

$//$ Creates an empty BST object.

$\{$

root $=$ null;

$\}$

public boolean isEmpty$()$

$//$ Returns true if this BST is empty; otherwise, returns false.

$\{$

return $($root $==$ null$)$;

$\}$

private int recSize$($BSTNode node$)$

$//$ Returns the number of elements in tree.

$\{$

if $($node $==$ null$)$

return $0$;

else

return recSize$($node$.$getLeft$())+$ recSize$($node$.$getRight$())+1$;

$\}$

public int size$()$

$//$ Returns the number of elements in this BST$.$

$\{$

return recSize$($root$)$;

$\}$

private boolean recContains$($T element, BSTNode node$)$

$//$ Returns true if tree contains an element e such that

$//$ e$.$compareTo$($element$)==0$; otherwise, returns false.

$\{$

if $($node $==$ null$)$

return false; $//$ element is not found

else if $($element$.$compareTo$($node$.$getInfo$())<mtext></mtext><mn>0</mn><mi>)</mi>$

return recContains$($element$,$ node.getLeft$())$; $//$ Search left subtree

else if $($element$.$compareTo$($node$.$getInfo$())>0)$

return recContains$($element$,$ node.getRight$())$; $//$ Search right subtree

else

return true; $//$ element is found

$\}$

public boolean contains $($T element$)$

$//$ Returns true if this BST contains an element e such that

$//$ e$.$compareTo$($element$)==0$; otherwise, returns false.

$\{$

return recContains$($element$,$ root$)$;

$\}$

private T recGet$($T element, BSTNode node$)$

$//$ Returns an element e from tree such that e$.$compareTo$($element$)==0$;

$//$ if no such element exists, returns null.

$\{$

if $($node $==$ null$)$

return null; $//$ element is not found

else if $($element$.$compareTo$($node$.$getInfo$())<mtext></mtext><mn>0</mn><mi>)</mi>$

return recGet$($element$,$ node.getLeft$())$; $//$ get from left subtree

else

if $($element$.$compareTo$($node$.$getInfo$())>0)$

return recGet$($element$,$ node.getRight$())$; $//$ get from right subtree

else

return node.getInfo$()$; $//$ element is found

$\}$

public T get$($T element$)$

$//$ Returns an element e from this BST such that e$.$compareTo$($element$)==0$;

$//$ if no such element exists, returns null.

$\{$

return recGet$($element$,$ root$)$;

$\}$

private BSTNode recAdd$($T element, BSTNode node$)$

$//$ Adds element to tree; tree retains its BST property.

$\{$

if $($node $==$ null$)$

$//$ Addition place found

node $=$ new BSTNode$($element$)$;

else if $($element$.$compareTo$($node$.$getInfo

node.setLeft$($recAdd$($element$,$ node.getLeft$()))$; $//$ Add in left subtree

else

node.setRight$($recAdd$($element$,$ node.getRight$()))$; $//$ Add in right subtree

return node;

$\}$

public void add $($T element$)$

$//$ Adds element to this BST$.$ The tree retains its BST property.

$\{$

root $=$ recAdd$($element$,$ root$)$;

$\}$

private T getPredecessor$($BSTNode node$)$

$//$ Returns the information held in the rightmost node in tree

$\{$

while $($node$.$getRight$()!=$ null$)$

node $=$ node.getRight$()$;

return node.getInfo$()$;

$\}$

private BSTNode removeNode$($BSTNode node$)$

$//$ Removes the information at the node referenced by tree.

$//$ The user's data in the node referenced by tree is no

$//$ longer in the tree. If tree is a leaf node or has only

$//$ a non$-$null child pointer, the node pointed to by tree is

$//$ removed; otherwise, the user's data is replaced by its

$//$ logical predecessor and the predecessor's node is removed.

$\{$

T data;

if $($node$.$getLeft$()==$ null$)$

return node.getRight$()$;

else if $($node$.$getRight$()==$ null$)$

return node.getLeft$()$;

else

$\{$

data $=$ getPredecessor$($node$.$getLeft$())$;

node.setInfo$($data$)$;

node.setLeft$($recRemove$($data$,$ node.getLeft$()))$;

return node;

$\}$

$\}$

private BSTNode recRemove$($T element, BSTNode node$)$

$//$ Removes an element e from tree such that e$.$compareTo$($element$)==0$

$//$ and returns true; if no such element exists, returns false.

$\{$

if $($node $==$ null$)$

found $=$ false;

else if $($element$.$compareTo$($node$.$getInfo$())<mtext></mtext><mn>0</mn><mi>)</mi>$

node.setLeft$($recRemove$($element$,$ node.getLeft$()))$;

else if $($element$.$compareTo$($node$.$getInfo$())>0)$

node.setRight$($recRemove$($element$,$ node.getRight$()))$;

else

$\{$

node $=$ removeNode$($node$)$;

found $=$ true;

$\}$

return node;

$\}$

public boolean remove $($T element$)$

$//$ Removes an element e from this BST such that e$.$compareTo$($element$)==0$

$//$ and returns true; if no such element exists, returns false.

$\{$

root $=$ recRemove$($element$,$ root$)$;

return found;

$\}$

$//$Preorder traversal

public void preorder$()\{$

System.out.println$("$

Preorder Traversal: $")$;

if$($root$==$null$)$

System.out.println$("$Tree is empty"$)$;

else $\{$

recPreorder$($root$)$;

$\}$

$\}$

private void recPreorder$($BSTNode node$)\{$

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

System.out.print$($node$.$getInfo$()+"")$;

recPreorder$($node$.$getLeft$())$;

recPreorder$($node$.$getRight$())$;

$\}$

$\}$

$//$Inorder traversal

public void inorder$()\{$

System.out.println$("$

Inorder Traversal: $")$;

if$($root$==$null$)$

System.out.println$("$Tree is empty"$)$;

else $\{$

recInorder$($root$)$;

$\}$

$\}$

private void recInorder$($BSTNode node$)\{$

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

recIno