$1.$ Write a Java program implementing a Binary Tree which stores a set of integer numbers. $($Not have

duplicate nodes$)$

$1)$ Define the BinaryTree interface

$2)$ Define the Node class

$$ Instance Variables

o E element$-($generics framework$)$

o Node Parent$($pointer$)$: reference to the parent node $($Self$-$referential$)$

o Node left$($pointer$)$: reference to the left child node $($Self$-$referential$)$

o Node right$($pointer$)$: reference to the right child node $($Self$-$referential$)$

$$ Constructor

$$ Methods

o E getElement$()//$Return the value of this node

o Node getParent$()//$Return the reference of the parent node

o Node getLeft$()//$Return the reference of left child node

o NodegetRight$()//$Return the reference of right child node

o setElement$($E e$)//$ Set value to this node

o setParent$($Node v$)//$Set reference to the parent node

o setLeft$($Node v$)//$Set reference to left child node

o setRight$($Node v$)//$Set reference to right node

$3)$ Define the class LinkedBinaryTree which implements BinaryTree Interface

$$ Instance Variables

o Node root $//$root of the tree.

o int size $//$number of nodes in the tree

$$ Constructor

$$ Methods

o int size$()//$returns the number of nodes that are contained in the tree

o Boolean isEmpty$()//$returns true if the tree does not contain any nodes

o Node root$()//$returns the reference of the root of the tree $($or null if empty$)$

o Node parent$($Node v$)//$returns the reference of the parent of node v $($or null if

v is the root$)$

o int numChildren$($Node v$)//$returns the number of children of node v

o Boolean isInternal$($Node v$)//$returns true if node v has at least one child

o Boolean isExternal$($Node v$)//$returns true if node v does not have any children

o Boolean isRoot$($Node v$)//$returns true if node v is the root of the tree

o Node left$($v$)//$returns the reference of the left child of node v; error if v has no

left child

o Node right$($v$)//$returns the reference of the right child of node v; error if v has

no right child

o Node sibling$($v$)//$Returns the reference of the sibling of node v$($or null if v has

no sibling$)$

o Boolean hasLeft$($v$)//$test whether node v has a left child

o Boolean hasRight$($v$)//$test whether node v has a right child

o Node addRoot$($E e$)//$creates a root for an empty tree, storing e as the element,

and returns the reference of that root; an error occurs if the tree is not empty

o Node addLeft$($Node v$,$ E e$)//$creates a left child of node v$,$ storing element e$,$

and returns the reference of the new node; an error occurs if v already has a

left child

o Node addRight$($Node v$,$ E e$)//$creates a right child of node v$,$ storing element

e$,$ and returns the reference of the new node; an error occurs if v already has a

right child

o E set$($Node v$,$ E e$)//$Replaces the element stored at node v with element e$,$ and

returns the previously stored element.

o E remove$($Node v$)//$Removes the node v$,$ replacing it with its child $($if any$),$

and returns the element that had been stored at v; an error occurs if v has two

children

$4)$ Define the class TestLinkedBinaryTree which tests all function $($if applicable$)$ of

LinkedBinaryTree