You have been learning about Binary Search Trees [BSTs). BSTs contain internal nodes holding data that can be sorted based on a key value. (For the upcoming homework, involving a Leaderboard, the key value will be an integer representing a player's unique ID number, or their current highest score.) In the lecture you also saw how an Iterator can facilitate traversing a data structure. For tonight's lab, instead of storing Integers at each node of a tree, let's store "Words." An instance of Word consists of a String plus an Integer representing the number of times that particular String appears in a given document. First, create and test the Word class itself. You will need getters and setters for its String value and its frequency of occurrence. When a Word is added to the tree, if it appears more than once, then the existing node should have its frequency-of-occurrence field updated, rather than creating additional instance nodes.
a. Implement a BST that traverses a ListArray of Strings and stores them as Word elements in lexicographic ("alphabetical") order based on ASCII code. Do not add duplicates; instead, but update the frequency count as needed. Assume these are valid English words.
b. Implement a second BST that stores the Words in the order of their frequency of occurrence.
c. Provide methods to find the most and least frequently occurring.
d. (OPTIONAL] Provide a method that accepts a String (e.g., representing a Sentence) and parses it into a ListArray of word Strings for submission to "a" above.
e. [OPTIONAL] Provide a method to find and print all words starting with the same first letter, sorted by frequency of occurrence.