NEED HELP ASAP with BST.java and BSTMap.java linked list and tree code below

AMap is a type of collection that associates a key with a value. The mapping of keys to values can be accomplished using different underlying data structures. In this three-part assignment, you will be working with two such data structures and then using them to implement aMap. One is called aLinked List and the other is called aTree.

Atree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to root. ABinary Search Tree (BST) is a specific type of tree where each node can only have up to two children, and all of the data values in the left subtree of any node is always less than the node value and all of the data values in the right subtree of any node is always to the right of the node value.

In part III, you will be implementing a BST, and then creating a Map that uses the BST to store and retrieve entries. As before,your Map should only use the BST by calling its methods. It should not touch inner variables like root or create node objects itself. That is the BST's job to do internally.

Since the key-value pairs stored in the map could be of any type, we will be usingGenerics to implement all our classes. For example, we could have < "Andrew", 1> as a key-value pair (which is of type ) and we could also have < 432, 34> as a key-value pair (which is of type ). Hence, it is important that we provide a way to reuse the same code with different inputs.Generics enabletypes (classes and interfaces) to be parameters when defining classes, interfaces and methods. Much like the more familiarformal parametersused in method declarations, type parameters provide a way for you to re-use the same code with different inputs. The difference is that the inputs to formal parameters are values, while the inputs to type parameters are types.

Note: You areNOT allowed to use any built-in Java data structures for any part of this assignment.

Program and Starter Code

You are being provided with starter code which is an interface representing aTree. You can find it in the course public folder (public/7P). It contains the signatures of the methods that you need to implement. Do not changeTree.java. You will also needMap.java from previous parts of this project.

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.

OPTIONAL: public static void main( String[] args )

Provides a user interface for creating and manipulating a BST ofStrings. Includes a command for each of the methods above.It should exit when a user enters the commandx.

Command	Method
a	add( T value )
c	contains( Object o )
C	clear()
g	get( Object o )
s	size()
e	isEmpty()
r	remove( Object o )

BSTMap.java inner class Entry

Note: Your code may generate warnings about "unchecked call to compareTo" inBSTMap.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 will need to createBSTMap.java. It will declare a classBSTMap, (declared aspublic class BSTMap implements Map .) When you begin writing the BSTMap class, you will first need to define its own inner classEntry (declared aspublic class Entry implements Map.Entry, Comparable .) It will need to implement the following methods:

public Entry( K key, V value )

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

public K getKey()

Returns this entry's key.

public V getValue()

Returns this entry's value.

public String toString()

Returns a string representation of this Entry. It should follow this format:(key, value)

public boolean equals( Object o )

Compares an objecto to this entry. If the object is anEntry (you can detect this usingo instanceof Entry), first casto to a variable of typeEntry, then return whether its key and value both match this entry's key and value. Otherwise, return whethero equals this entry's key.Required for testing.

public int compareTo( Object o )

Compares an objecto to this entry. If the object is anEntry (you can detect this usingo instanceof Entry), first casto to a variable of typeEntry and then return the result of thecompareTo method between this entry's key ando's. Otherwise, return the result ofcompareTo between this entry's key ando.

BSTMap.java

Your BSTMap class should use an instance variable of type BST to store its entries. Note that BSTMap should only call methods from BST,BSTMap should not edit the BST's nodes directly. You have to implement the following methods for theBSTMap class:

public BSTMap( )

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

public BST> getTree()

Returns the BST being used by this map.Mostly used for testing purposes.

public V put( K key, V value )

Associates the given key with the given value in the map. Should not add duplicate items to the map. If the map previously contained a mapping for the key, the old value is replaced by the specified value.

public V putIfAbsent( K key, V value )

If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.

public String toString()

Returns a string representation of this BSTMap. It should be in the same format as the BST toString described above.

public void clear( )

Removes all of the elements from this map.

public V get( K key )

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

public boolean containsKey( K key )

Returns true if this map contains a mapping for the specified key.

public boolean isEmpty( )

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

public V remove( K key )

Removes the mapping for a key from this map if it is present. Returns the value to which this map previously associated the key, or null if the map contained no mapping for the key.

public int size( )

Returns the number of elements in this map.

OPTIONAL: public static void main( String[] args )

Provides a user interface for creating and manipulating a Map ofStrings toIntegers. Includes a command for each of the methods above.It should exit when a user enters the commandx.

Command	Method
p	put( K key, V value )
P	putIfAbsent( K key, V value )
c	containsKey( K key )
C	clear()
g	get( K key )
s	size()
e	isEmpty()
r	remove( K key )

public class LinkedList { Node head; // head of the list // LinkedList Node. static class Node { T data; Node next; // Constructor Node(T data) { this.data = data; this.next = null; } } // Method to insert a new node public static  LinkedList insert(LinkedList list, T data) { // Create a new node with given data Node new_node = new Node<>(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static  void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } System.out.println(" "); } }

public interface Tree { /** * Appends the specified value to this tree. Does not allow duplicates. * * @param value T The value to add * @return boolean True if the value is inserted, false otherwise */ boolean add(T value); /** * Removes all of the elements from this tree. */ void clear(); /** * Returns true if this tree contains the specified element. * * @param o Object The element to check if present in the tree * @return boolean */ boolean contains( Object o ); /** * Returns the element that matches the object parameter in this tree. * * @param o Object to search the tree for matching elements. * @return T */ T get(Object o); /** * Removes the first occurrence of the specified element from this * tree, if it is present. * If tree does not contain the element, it is unchanged. * Returns true if this tree contained the specified element * (or equivalently, if this tree changed as a result of the call). * * @param o element to be removed from this tree, if present * @return true if this tree contained the specified element */ boolean remove(Object o); /** * Returns true if this tree contains no elements. * * @return true if this tree contains no elements */ boolean isEmpty(); /** * Returns the number of elements in this tree. * @return int */ int size(); /** * Inner interface to represent a Tree node. */ public interface Node { /** * Set the value of this node. * @param value Value */ public void setValue(T value); /** * Get the value of this node. * * @return T Value */ public T getValue( ); } }