Implementing a Binary Search Tree in Java (incl. writing tests)

I need someone who can implement the following in Java:

FYI: This project needs expertise in data structures (specifically binary search trees), the implementation in Java is pretty basic.

You will be building a data structure on top of (ordinary) Binary Search Trees. You should be using and extending a given (I will provide the Java files) implementation of BSTs. The BSTs in question carry int keys, and every key in a tree is unique (there are variants of BSTs that allow keys to occur multiple times, but not this one). An empty tree is represented as null.

The overall goal is to add the three following capabilities to the implementation:

• We want an OO-type Tree for trees that serves as the general interface for trees for users of trees. The actual links sit inside that class.
• In anticipation of later doing more sophisticated things with our trees, we want that our links carry parent references. Thus each link should know either the Link node that has it as its left/right child or if the link is the root: it has the Tree object as its parent.
• One useful information is the size of a subtree that has a particular Link as its local root. To avoid having to recompute it we want to memoize the information by storing it in a field. This requires some effort to maintain the information when the respective subtree is modified.

1. Write the interface Parent. This should have a method void resize() which is supposed to be invoked by when (one of) the children changes size.
2. Write the class Tree. In particular:
(a) Write a constructor to create/host an empty tree. The class needs to have a field of type Link for the root of the hosted tree. It needs to implement the Parent interface in a sensible way.
(b) Write the method public void insert(int k) which inserts k into the tree. This should use the insert method of class Link.
(c) Write the method public boolean find(int k) which checks whether k is present in the tree. This should use the method find of the Link class.
(d) Write the method public int size() which returns the size of the tree (number of keys).
3. Modify the class Link in the following way.
(a) We need two additional fields, one for keeping a parent, and one for memoizing the size. The class should implement the Parent interface in a sensible way. Eventually, you should be able to assume that the Parent field is never empty except when a Link has been freshly created.
1
(b) Provide a public void setParent(Parent p) method to set the parent of a Link.
(c) Modify the code of Link (and/or Tree) to set parent information where (potentially)
new cells spring into life.
(d) Modify the code of Link (and/or Tree) to keep the size information up-to-date.
(e) Write a method static public int size(Link t) which computes the size of (num- ber of keys in) the link t. This method should trust that the memoized size field is correct.
4. We want to be able to test whether our parent pointers are correct and complete. Write a methodboolean checkLinks()intheTreeclasswhichcheckswhetheralltheparentlinksin its tree are present and correct, and returns true if it is the case, and false otherwise. This method will need an accompanying method in the Link class, which you need to determine.