solve below questions. There should be two coding is created. BSTNode.java BST.java Binary Search Tree you will

Fantastic news! We've Found the answer you've been seeking!

Question:

solve below questions. There should be two coding is created.

BSTNode.java

BST.java

Binary Search Tree

you will be coding theadd()andremove()methods of abinary search tree. A binary search tree, or BST, is a collection of nodes, each having a data item and a reference pointing to a left and a right child node.The BST must adhere to thefollowing order property: for any given node, its left child's data and all of its children's data must be less than the current node while its right child's data and all of its children's data must be greater than the current node. In order to compare the data, all elements added to the tree must implement Java's genericComparableinterface.Since trees are naturally recursive structures, each of these methods should beimplemented recursively.

IMPORTANT:

You will begiven unlimited attempts on this assignment, withno cooldownbetween submissions.
Please run your code before each submission to ensure that there are no formatting errors! If there are formatting errors in your code, your code will not be graded and a submission attempt will be logged. For more information, please review the Vocareum overview below.

BSTNode

ABSTNodeclass is provided to you and will be used to represent the nodesin the tree. This fileshould be treated asread-onlyand should not be modified in any way. This BSTNode class contains getter and setter methods to access and mutate the structure of the nodes. Please make sure that you understand how this class works, as interaction with this class is crucial forthisassignment.

Pointer Reinforcement

Since both the add() and remove() methods may change the structure of the tree, we highly recommend that you use a technique called pointer reinforcement. Although using pointer reinforcement is not required, it will help to make your code cleaner, and it'll also help greatly in future assignments if you end up taking the next course in our series! Below is a video created by our 1332 TAs,timestamped to a section on pointer reinforcement.

Pointer Reinforcement Overview

Comparable

As stated, the data in the BST must implement the Comparable interface. As you'll see in the les, the generic typing has been specified to require that it implements theComparableinterface. You use the interface by making a method call likedata1.compareTo(data2). This will return anint, and the value tells you howdata1anddata2are in relation to each other.

If the int ispositive, then data1 islargerthan data2.
If the int isnegative, then data1 issmallerthan data2.
If the int iszero, then data1equalsdata2.

Note that the returned value can beanyinteger in Java's int range,notjust -1, 0, 1.

Successor

Recall that earlier in the modules you learned about the successor and predecessor of a node in a tree. As a refresher, the successor of a node, n, is the node in the tree that contains the smallest data that is larger than n's data. The predecessor of a node, n, is the node in the tree that contains the largest data that is smaller than n's data. When removing a node from a BST that has two children, we can choose to replace the removed node with either it's successor or predecessor. For the 2-child case in remove(), you will be replacing the removed node with itssuccessor node,NOTthe predecessor node. For more details, please refer to the javadocs for remove().

Helper Methods

You'll also notice that the public method stubs we've provided do not contain the parameters necessary for recursion to work, so these public methods should act as "wrapper methods" for you to use. You will have to write private recursive helper methods and call them in these wrapper methods. All of these helper methodsmust be private. To reiterate, donotchange the method headers for the provided methods.