public abstract class DupBinaryTree implements DupBinaryTreeADT $\{$

$//======================================================================//$

$//$Definition of the DupBinaryTreeNode class

protected class DupBinaryTreeNode $\{$

public T info;

public DupBinaryTreeNode lLink;

public DupBinaryTreeNode mLink;

public DupBinaryTreeNode rLink;

$//[7\mathrm{.}5$pts$]$ Default constructor

public DupBinaryTreeNode$()\{$

this.info $=$ null;

this.lLink $=$ null;

this.mLink $=$ null;

this.rLink $=$ null;

$\}$

$//[7\mathrm{.}5$pts$]$ Alternate constructor

public DupBinaryTreeNode$($T item, DupBinaryTreeNode left, DupBinaryTreeNode middle, DupBinaryTreeNode right$)\{$

this.info $=$ item;

this.lLink $=$ left;

this.mLink $=$ middle;

this.rLink $=$ right;

$\}$

$//-----------------------------//$

$//$ clone$()$ method

public Object clone$()\{$

DupBinaryTreeNode copy $=$ null;

try $\{$

copy $=($DupBinaryTreeNode$)$ super.clone$()$;

$\}$ catch $($CloneNotSupportedException e$)\{$

return null;

$\}$

return copy;

$\}$

$//-----------------------------//$

$//$ toString$()$ method

public String toString$()\{$

return info.toString$()$;

$\}$

$\}//$ End of class DupBinaryTreeNode

$//======================================================================//$

$//-----------------------------//$

$//$Instance variable vor class DupBinaryTree

protected DupBinaryTreeNode root;

$//-----------------------------//$

$//$Default constructor

public DupBinaryTree$()\{$

root $=$ null;

$\}$

$//-----------------------------//$

public Object clone$()\{$

DupBinaryTree copy $=$ null;

try $\{$

copy $=($DupBinaryTree$)$ super.clone$()$;

$\}$ catch $($CloneNotSupportedException e$)\{$

return null;

$\}$

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

copy.root $=$ copyTree$($root$)$;

return copy;

$\}$

$//-----------------------------//$

$//$ Helper method called by clone

private DupBinaryTreeNode copyTree$($DupBinaryTreeNode otherTreeRoot$)\{$

DupBinaryTreeNode temp;

if $($otherTreeRoot $==$ null$)$

temp $=$ null;

else $\{$

temp $=($DupBinaryTreeNode$)$ otherTreeRoot.clone$()$;

temp.lLink $=$ copyTree$($otherTreeRoot$.$lLink$)$;

temp.mLink $=$ copyTree$($otherTreeRoot$.$mLink$)$;

temp.rLink $=$ copyTree$($otherTreeRoot$.$rLink$)$;

$\}$

return temp;

$\}$

$//-----------------------------//$

$//$ Function to print the sorted tree without duplicates values

$//$ Input: $+$ Nothing

$//$ Output: $+$ The sorted tree without duplicates values

$//-----------------------------//$

public void printSortedTreeWithoutDuplicates$()\{$

printDistinct$($root$)$;

$\}$

$//-----------------------------//$

$//-----$ TO BE IMPLEMENTED $-----//$

$//-----------------------------//$

$//[10$pts$]$

$//$ Function to print the sorted tree without duplicates values

$//$ Input: $+$ DupBinaryTreeNode t : The current node in the tree

$//$ Output: $+$ Nothing $($void$)$

$//-----------------------------//$

public void printDistinct$($DupBinaryTreeNode t$)\{$

$\}$

$//-----------------------------//$

$//$ Function to print the sorted tree with duplicates values

$//$ Input: $+$ Nothing

$//$ Output: $+$ The sorted tree without duplicates values

$//-----------------------------//$

public void printSortedTreeWithDuplicates$()\{$

printDup$($root$)$;

$\}$

$//-----------------------------//$

$//-----$ TO BE IMPLEMENTED $-----//$

$//-----------------------------//$

$//[10$pts$]$

$//$ Function to print the sorted tree with duplicates values

$//$ Input: $+$ DupBinaryTreeNode t : The current node in the tree

$//$ Output: $+$ Nothing $($void$)$

$//-----------------------------//$

public void printDup$($DupBinaryTreeNode t$)\{$

$\}$