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. (STARTER CODE BELOW)

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 )

/** * Specification for a Tree ADT. * @author Sofia Lemons * @version 04/11/2019 * @param  Type */ 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( ); } }

/** * Specification for a Map ADT. * @author Shubham Chatterjee * @version 03/07/2019 * @param  Key type * @param  Value type */ public interface Map { /** * Removes all of the mappings from this map. * The map will be empty after this call returns. */ void clear(); /** * Returns true if this map contains a mapping for the specified key. * @param key key whose presence in this map is to be tested * @return true if this map contains a mapping for the specified key */ boolean containsKey(K key); /** * Returns the value to which the specified key is mapped, * or null if this map contains no mapping for the key. * If this map permits null values, then a return value of null does not necessarily indicate * that the map contains no mapping for the key; * it's also possible that the map explicitly maps the key to null. * The Map#containsKey operation may be used to distinguish these two cases. * @param key the key whose associated value is to be returned * @return the value to which the specified key is mapped, * or null if this map contains no mapping for the key */ V get(K key); /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, * the old value is replaced by the specified value. * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or null if there was * no mapping for key. * (A null return can also indicate that the map previously associated * null with key, if the implementation supports null values.) */ V put(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. * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or null if there * was no mapping for key. * (A null return can also indicate that the map previously associated * null with key, * if the implementation supports null values.) */ V putIfAbsent(K key, V value); /** * Returns true if this map contains no key-value mappings. * @return true if this map contains no key-value mappings */ boolean isEmpty(); /** * 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. * If this map permits null values, then a return value of null does not necessarily indicate * that the map contained no mapping for the key; * it's also possible that the map explicitly mapped the key to null. * The map will not contain a mapping for the specified key once the call returns. * @param key key whose mapping is to be removed from the map * @return the previous value associated with key, or null if there was no mapping for key. */ V remove(K key); /** * Returns the number of key-value mappings in this map. * @return the number of key-value mappings in this map */ int size(); /** * Specification of an entry in the map. * @param  Key type * @param  Value type */ interface Entry { /** * Returns the key corresponding to this entry. * @return the key corresponding to this entry */ K getKey(); /** * Returns the value corresponding to this entry. * @return the value corresponding to this entry */ V getValue(); } }

not sure if you need linked list but if so use this one not javas version

 import java.util.Scanner; /** * @author Anthony * @version 4/3/23 * @param  argument */ public class LinkedList extends List { Node head; Node tail; LinkedList() { head = null; tail = null; } /** * * @return head node */ public Node getHead() { return head; } /** * * @return tail node */ public Node getTail() { return tail; } /** * * @return gets the length of the node */ public int size() { Node temp = head; int size = 0; while (temp != null) { temp = temp.next; size++; } return size; } /** * * @param value T The value to add * @return true if the word was added */ public boolean add(T value) { if (contains(value)) { return false; } Node temp = new Node(value); if (tail == null) { head = temp; tail = temp; } else { temp.prev = tail; tail.next = temp; tail = temp; } return true; } /** * * @param index Integer The index at which to insert * @param value T The value to insert */ public void add(int index, T value) { if (contains(value) || index < 0) { return; } else if (index >= size()) { add(value); //System.out.println("here2"); return; } if (contains(value)) { return; } Node temp = new Node(value); Node current = head; if (index == 0) { temp.next = current; if (head == null) { head = temp; tail = temp; } else { current.prev = temp; head = temp; } return; } int length = 0; while (current != null) { current = current.next; length++; } if (length >= size()) { tail.next = temp; tail.prev = tail; tail = temp; } else { current.prev.next = temp; temp.prev = current.prev; current.prev = temp; temp.next = current; return; } } /** * * @return a string */ public String toString() { StringBuilder s = new StringBuilder(); s.append("["); Node current = head; while (current != null) { s.append(current.value); current = current.next; if (current != null) { s.append(", "); } } s.append("]"); return s.toString(); } /** * */ public void clear() { head = null; tail = null; } /** * * @param index Integer The index at which to insert * @return nothing */ public T get(int index) { if (index < 0) { return null; } Node current = head; int length = 0; while (current != null) { if (index == length) { return current.value; } current = current.next; length++; } return null; } /** * * @param o to search for * @return nothing */ public T get(Object o) { Node current = head; while (current != null) { if (current.value.equals(o)) { return current.value; } current = current.next; } return null; } /** * * @param o Object The element to check if present in the list * @return true in object o is contained */ boolean contains(Object o) { if (get(o) == null) { return false; } return true; } /** * * @return true if empty */ public boolean isEmpty() { if (head == null) { return true; } return false; } /** * * @param index the index of the element to be removed * @return nothing */ public T remove(int index) { Node current = head; if (index < 0 || index >= size() || head == null) { return null; } else if (index == 0) { if (head == tail) { head = null; tail = null; } else { head = head.next; head.prev = null; current.next = null; } return current.value; } else if (index == size() - 1) { Node temp = tail; tail = tail.prev; tail.next = null; temp.prev = null; return temp.value; } int length = 0; while (current != null) { if (index == length) { current.next.prev = current.prev; current.prev.next = current.next; current.prev = null; current.next = null; return current.value; } current = current.next; length++; } return null; } /** * * @param o element to be removed from this list, if present * @return true if removed */ public boolean remove(Object o) { Node current = head; int length = 0; while (current != null) { if (o.equals(current.value)) { remove(length); return true; } current = current.next; length++; } return false; } /** * * @param args main arguments */ public static void main(String[] args) { int entry = 0; int exit = 0; Scanner scan = new Scanner(System.in); String test = scan.nextLine(); //System.out.println("= " + test); char ch = test.charAt(0); LinkedList link = new LinkedList(); while (ch != 'x') { //scan.nextLine(); //adds value if (ch == 'a') { int temp = test.length(); //System.out.println(temp + " temp"); if (entry == 0) { if (!link.contains(test.substring(1, temp))) { link.add(test.substring(1, temp)); System.out.println(link.toString()); //link.add(1, "testcase"); //System.out.println("here"); entry = 1; } } if (exit == 1) { String str = scan.nextLine(); //link.add(str.substring(2,temp)); link.add(str); System.out.println(link.toString()); } exit = 1; //adds value at given index } else if (ch == 'A') { int num = scan.nextInt(); String s = scan.nextLine(); //System.out.println("here1"); link.add(num, s); System.out.println("num " + num); System.out.println("s " + s); System.out.println(link.toString()); //check if it contains object o } else if (ch == 'c') { System.out.println(link.contains(scan.nextLine())); //clears nodes } else if (ch == 'C') { link.clear(); System.out.println(link.toString()); //gets the index } else if (ch == 'g') { System.out.println(link.get(scan.nextInt())); //size } else if (ch == 's') { System.out.println(link.size()); //checks if nodes are empty } else if (ch == 'e') { System.out.println(link.isEmpty()); //removes the object o } else if (ch == 'r') { link.remove(scan.nextLine()); System.out.println(link.toString()); //removes index } else if (ch == 'R') { link.remove(scan.nextInt()); System.out.println(link.toString()); } ch = scan.next().charAt(0); } } }