bst,java linkedlist.java and tree.java are below

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(" "); } }

import java.util.ArrayList; import java.util.List; public class BST> implements Tree { private BST.TreeNode root; public BST() { root = null; } private class TreeNode implements Node { T value; TreeNode left; TreeNode right; TreeNode parent; public TreeNode(T value) { this.value = value; left = null; right = null; parent = null; } public void setValue(T value) { this.value = value; } public T getValue() { return value; } } // Add a node public boolean add(T value) { if (root == null) { root = new TreeNode<>(value); return true; } else { return addRecursive(root, value); } } private boolean addRecursive(Node current, T value) { TreeNode currentNode = (TreeNode) current; int comparison = value.compareTo(currentNode.getValue()); if (comparison == 0) { // Equal values are not allowed return false; } else if (comparison < 0) { if (currentNode.left == null) { currentNode.left = new TreeNode<>(value); return true; } else { return addRecursive(currentNode.left, value); } } else { if (currentNode.right == null) { currentNode.right = new TreeNode<>(value); return true; } else { return addRecursive(currentNode.right, value); } } } // Clear the tree public void clear() { root = null; } // Check if the tree contains a value public boolean contains(Object o) { return containsRecursive(root, (T) o); } private boolean containsRecursive(Node current, T value) { if (current == null) { return false; } TreeNode currentNode = (TreeNode) current; int comparison = value.compareTo(currentNode.getValue()); if (comparison == 0) { return true; } else if (comparison < 0) { return containsRecursive(currentNode.left, value); } else { return containsRecursive(currentNode.right, value); } } // Get a value from the tree public T get(Object o) { return getRecursive(root, (T) o); } private T getRecursive(Node current, T value) { if (current == null) { return null; } TreeNode currentNode = (TreeNode) current; int comparison = value.compareTo(currentNode.getValue()); if (comparison == 0) { return currentNode.getValue(); } else if (comparison < 0) { return getRecursive(currentNode.left, value); } else { return getRecursive(currentNode.right, value); } } // Remove a value from the tree // Remove a value from the tree public boolean remove(Object o) { if (contains(o)) { root = removeRecursive(root, (T) o); return true; } else { return false; } } private TreeNode removeRecursive(TreeNode current, T value) { if (current == null) { return null; } if (value.equals(current.getValue())) { // Node to delete found // ... code to delete the node will go here if (current.left == null && current.right == null) { // a) Node to remove has no children return null; } else if (current.right == null) { // b) Node to remove has only a left child return current.left; } else if (current.left == null) { // c) Node to remove has only a right child return current.right; } else { // d) Node to remove has two children T smallestValue = findSmallestValue(current.right); current.setValue(smallestValue); current.right = removeRecursive(current.right, smallestValue); return current; } } if (value.compareTo(current.getValue()) < 0) { current.left = removeRecursive(current.left, value); return current; } current.right = removeRecursive(current.right, value); return current; } private T findSmallestValue(TreeNode root) { return root.left == null ? root.getValue() : findSmallestValue(root.left); } // Check if the tree is empty public boolean isEmpty() { return root == null; } // Get the size of the tree public int size() { return sizeRecursive(root); } private int sizeRecursive(TreeNode current) { return current == null ? 0 : sizeRecursive(current.left) + 1 + sizeRecursive(current.right); } public void inOrder(TreeNode node, List result) { if (node == null) { return; } inOrder(node.left, result); // Visit left subtree result.add(node.value); // Visit root inOrder(node.right, result); // Visit right subtree } public List inOrder() { List result = new ArrayList<>(); inOrderRecursive(root, result); return result; } private void inOrderRecursive(TreeNode node, List result) { if (node == null) { return; } inOrderRecursive(node.left, result); // Visit left subtree result.add(node.value); // Visit root inOrderRecursive(node.right, result); // Visit right subtree } @Override public String toString() { StringBuilder sb = new StringBuilder(); toStringRecursive(root, sb, 0); String toReturn = sb.toString(); return toReturn; } private void toStringRecursive(TreeNode node, StringBuilder sb, int level) { if (node == null) { return; } // Indentation for the current level for (int i = 0; i < level * 6; i++) { sb.append(" "); } // Node label (L for left child, R for right child) if (level > 0) { TreeNode parent = getParent(node); sb.append(parent.left == node ? "L " : "R "); } // Node value sb.append(node.value).append(" "); // Recursive calls for left and right subtrees with increased level toStringRecursive(node.left, sb, level + 1); toStringRecursive(node.right, sb, level + 1); } private TreeNode getParent(TreeNode node) { return findParentRecursive(root, node); } private TreeNode findParentRecursive(TreeNode current, TreeNode node) { if (current == null || current == node) { return null; } if (current.left == node || current.right == node) { return current; } TreeNode leftParent = findParentRecursive(current.left, node); if (leftParent != null) { return leftParent; } TreeNode rightParent = findParentRecursive(current.right, node); if (rightParent != null) { return rightParent; } return null; } }

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( ); } }