A binary search tree represents an ordered collection of data where each node holds one data item and has links to two subtrees, such that all data items in the left subtree come before the current data item and all data items in the right subtree come after the current data item. The tree with no data is represented as a leaf. The trees below demonstrate some (small!) valid and invalid examples of binary search trees over integers (the leaves of the tree are not shown): val'id: val'id: 'inval'id: 3 2 3 I \\ I \\ l \\ 2 4 1 4 1 4 / / / \\ 1 3 2 5 (In the last tree, even though the subtree beginning at 4 is a valid binary search tree on its own, the root node is not a valid binary search tree since 2 | + + | Comparator order ------------- + + + I I \\ | I l | _________________ I | | | + + + + I | Leaf | | Node I | + + + + I | T data I | | ABST left I | | ABST right I | + + I V + + + + | Book | | Comparator | + + + + | String title | | int compare(T tl, T t2) | | String author | + ------------------------- + | int price | + + Because every node in a BST must know about how the ordering works, we will use Java's Comparator interface, and use it as a field of the abstract base class of BST nodes and leaves. 0 Design the classes BooksByTitle, BooksByAuthor, and BooksByPrice that allow us to compare the books by their title, their author, or price respectively. String-based comparisons should be alphabetical; numeric comparisons should be by increasing value. 0 Design the classes that represent a binary search tree, following the class diagram shown above. The Node and Leaf constructors should take arguments in the order of its fields as above, starting with the inherited ones. Make examples of data, including binary search trees of Books. (In this example we use an abstract class, rather than an interface, because we need the order field). Please write comments above each example so that we know more about what examples you are creating. Design the method insert that takes an item and produces a new binary search tree with the given item inserted in the correct place. If the value is a duplicate according to the tree order, insert it into the right-side subtree. This should work for any of the comparators above. (Where should the newly created nodes obtain their ordering from?) Design the method present that takes an item and returns whether that item is present in the binary search tree. This method should use the Comparator object used to build the tree (i.e. if Books ByTitle is used, then this method returns true if there is a book with the same title as the item, etc.) Design the method getLeftmost that returns the leftmost item contained in this tree. In the Leaf class, you should throw an exception: throw new RuntimeException("No leftmost item of an empty tree\") Design the method getRight that returns the tree containing all but the leftmost item of this tree. In the Leaf class, you should throw an exception: throw new RuntimeException("No right of an empty tree") Design the method sameTree that determines whether this binary search tree is the same as the given one: that is, they have matching structure and matching data in all nodes. Design the method sameData that determines whether this binary search tree contains the same data in the same order as the given tree. Note: Given the following four trees: bstA : bstB: bstc: bstD: b3 b3 b2 b3 b2 b4 62 b4 b1 b4 b1 b4 - b1 b1 63 b5 the following should hold: obstA is the same Tree as bstB obstA is not the same Tree as bstC obstA is not the same Tree as bstD obstA has the sameData as bstB obstA has the sameData as bstC obstA does not have the sameData as bstD Hint: Articulate clearly (in plain language) when one BST has the same data as the another BST. Do the same for same Tree. This will give you any helper operations you may need. . Copy into your project the IList interface and its related classes. Make examples of IList, including examples that contain the same books (in the same order) as some of your binary search trees. . Design the method buildList for the classes that represent the binary search tree of type T that produces a list of items in the tree in the sorted order. Hint: Draw a simple BST with 2 or 3 items, and the expected output of buildList. Now think about how to produce this list, given the tree. Now try with bigger examples