BST.java inner class Node

You will need to createBST.java. It will declare a classBST, (declared asBST implements Tree .) This ensures that all data stored in your BST will have thecompareTo method. When you begin writing the BST class, you will first need to define its own inner classNode (declared aspublic class Nodeimplements Tree.Node .)You will need to add fields (such as the left child, right child, and parent) and possibly other methods to make it behave as a BST node. It will need to implement the following methods:

public Node( T value )

The constructor for Node. It should initialize any necessary fields.

public void setValue( T value )

Sets the value of this node to the given parameter.

public T getValue( )

Gets the value of this node.Required for testing.

public Node getLeft( )

Gets the left child of this node.Required for testing.

public Node getRight( )

Gets the right child of this node.Required for testing.

public Node getParent( )

Gets the parent of this node.Required for testing.

BST.java

Note: Your code may generate warnings about "unchecked call to compareTo" inBST.java. You can put@SuppressWarnings("unchecked") before the signature of any methods that use compareTo to suppress these warnings. We are bending some Java rules, so the compiler will warn you of that unless you use the above annotation.

You also have to implement the following methods for theBST class:

public BST( )

The constructor for BST. It should initialize any necessary fields.

public Node getRoot()

Returns the root of the BST.Required for testing.

public boolean add( T value )

Appends the specified value to the correct location in this BST. You should use thecompareTo method of the BST's nodes' data when comparing too. (You should not callo.compareTo(node.value), butnode.value.compareTo(o) for nodes' values in the tree.) Should not add duplicate items to the BST.

public String toString()

Returns a string representation of this BST using indentation to represent each "level" of the tree. The root should be the furthest left when the string is printed, its children should be indented by 6 spaces, their children by 12 spaces, etc. Each node other than the root should be labeled as L for left children and R for right children. For example:

L even

the

L undo

R word

L zag

R zig

R zoo

public void clear( )

Removes all of the elements from this BST.

public T get( Object o )

Returns the data that matches the object given. You should use thecompareTo method of the BST's nodes' data when comparing too. (You should not callo.compareTo(node.value), butnode.value.compareTo(o) for nodes' values in the tree.) Should returnnull if the object does not match any data in the BST.

public boolean contains( Object o )

Returns true if this BST contains the specified element, false otherwise. You should use thecompareTo method of the BST's nodes' data when comparing too. (You should not callo.compareTo(node.value), butnode.value.compareTo(o) for nodes' values in the tree.)

public boolean isEmpty( )

Returns true if this BST contains no elements, false otherwise.

public boolean remove( Object o )

Removes the specified element from this BST, if it is present. If this BST does not contain the element, it is unchanged. Returns true if this BST contained the specified element, false otherwise. When a node which is a left child of its parent and has both children is removed, its own left child should take its place. When a node which is a right child of its parent and has both children is removed, its own right child should take its place. When the root is removed and has both children, its left child should take its place. You should use thecompareTo method of the BST's nodes' data when comparing too. (You should not callo.compareTo(node.value), butnode.value.compareTo(o) for nodes' values in the tree.)

public int size( )

Returns the number of elements in this BST.