Implement a Sorted List using a Binary Search Tree

Hey everyone, I need someone to create a sorted list using a binary search tree (BST) for the code below. Please fill in the implementations of the methods below. /** * BSTSortedList.java - Shell for Assignment #5 */ import java.util.Iterator; import java.util.NoSuchElementException; import TreePackage.*;

public class BSTSortedList> implements SortedListInterface { private BinarySearchTree list; //the sorted list, represented as a BST private int numberOfEntries; //number of entries currently in list

//default constructor -- list is initially empty public BSTSortedList() { list = new BinarySearchTree<>(); numberOfEntries = 0; }

//FILL IN IMPLEMENTATION OF METHODS BELOW

public class SortedList { private static class Node { int val; Node left; Node right;

public Node(int val) { this.val = val; } }

private Node root; private int size;

public void add(int val) { if (root == null) { root = new Node(val); size++; return; }

Node curr = root; while (true) { if (val < curr.val) { if (curr.left == null) { curr.left = new Node(val); size++; return; } curr = curr.left; } else { if (curr.right == null) { curr.right = new Node(val); size++; return; } curr = curr.right; } } }

public int size() { return size; }

public List toList() { List list = new ArrayList<>(); inorder(root, list); return list; }

private void inorder(Node node, List list) { if (node == null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } }

}

For reference, here is the interface of the sorted list that will need to be used to fill in the methods for the code above:

/** An interface for the ADT sorted list. Entries in the list have positions that begin with 1. @author Frank M. Carrano @author Timothy M. Henry @version 5.0 */ public interface SortedListInterface> { /** Adds a new entry to this sorted list in its proper order. The list's size is increased by 1. @param newEntry The object to be added as a new entry. */ public void add(T newEntry); /** Removes the first or only occurrence of a specified entry from this sorted list. @param anEntry The object to be removed. @return True if anEntry was located and removed; otherwise returns false. */ public boolean remove(T anEntry); /** Removes the entry at a given position from this list. * Entries originally at positions higher than the given * position are at the next lower position within the list, * and the list's size is decreased by 1. @param givenPosition An integer that indicates the position of the entry to be removed. @return A reference to the removed entry. @throws IndexOutOfBoundsException if either givenPosition < 1 or givenPosition > getLength(). */ public T remove(int givenPosition); /** Retrieves the entry at a given position in this list. @param givenPosition An integer that indicates the position of the desired entry. @return A reference to the indicated entry. @throws IndexOutOfBoundsException if either givenPosition < 1 or givenPosition > getLength(). */ public T getEntry(int givenPosition); /** Gets the position of an entry in this sorted list. @param anEntry The object to be found. @return The position of the first or only occurrence of anEntry if it occurs in the list; otherwise returns the position where anEntry would occur in the list, but as a negative integer. */ public int getPosition(T anEntry); /** Sees whether this list contains a given entry. @param anEntry The object that is the desired entry. @return True if the list contains anEntry, or false if not. */ public boolean contains(T anEntry); /** Removes all entries from this list. */ public void clear(); /** Gets the length of this list. @return The integer number of entries currently in the list. */ public int getLength(); /** Sees whether this list is empty. @return True if the list is empty, or false if not. */ public boolean isEmpty(); /** Retrieves all entries that are in this list in the order in which they occur in the list. @return A newly allocated array of all the entries in the list. If the list is empty, the returned array is empty. */ public T[] toArray(); }