Each node in the DupBinarySearchTree has its info, and three pointers: left $($lLink$),$ middle $($mLink$)$ and right

$($rLink$)$ links to point to nodes whose info are less than, exactly equal and greater than the current node. For

instance, the root with info $3$ has three links corresponding to nodes with info $2,3$ and $4$ as indicated in the

picture while the node with info $1$ and its three duplicates has only one middle link. The definition of tree height

on a BST also applies on DupBinarySearchTree. However, this tree only allows at most $5$ duplicate copies of

any node $($an error message should be generated if any node has more than $5$ copies$).$

Refer to Lecture $12$ for all the necessary classes. The client ClientDupBST.java is included to test your

program. Type parameter $($generic data type$)$ is required for all classes. Recursion is allowed for the final

exam. Keep in mind, there can $($and will$)$ be unexpected errors if you simply copy and paste code from the

lecture.

You will need to implement the following methods whose descriptions are given in the interface and the files.

A$.[40$pts total$]$ In file $$DupBinaryTree$.$java$$

$+[5$pts$]$ The default constructor.

$+[5$pts$]$ The alternative constructor.

$+[10$pts$]$ The helper method printDistinct$()$ for function printSortedTreeWithoutDuplicates$().$

$+[10$pts$]$ The helper method printDup$()$ for function printSortedTreeWithDuplicates$().$

$+[5$pts$]$ The helper method height$()$ for function treeHeight$().$

$+[5$pts$]$ The helper method isDupBST$()$ for function isDupBinarySearchTree$().$

B$.[60$pts total$]$ In file $$DupBinarySearchTree$.$java$$

$+[15$pts$]$ The helper method reSearch$()$ for function search$().$

$2$

$+[15$pts$]$ The helper method recInsert$()$ for function insert$().$

$+[15$pts$]$ The helper method recDelete$()$ for function delete$().$

$+[15$pts$]$ A method named findClosest$($ T key $)$ to return the node whose information is the closest $($in

absolute distance$)$ to the provided key. For example, in the above tree with information of type Double,

and key $=1\mathrm{.}71,$ the closest node is the one with information $2.$ Write code to test this method in the

provided client