This project is something that can easily be found on the Internet. Like most projects, it is graded on effort and the honor system. Please adhere to the honor system as, frankly, cheating won't help your grade and, more importantly, cheating will teach you nothing. 1. Write a BST<T extends Comparable<T>> class. class BST<T extends Comparable<T>> Fields (3) * private T datum * private BST<T> left * private BST<T> right Constructors (1) * BST(T datum) Accessors (3) * getDatum() // returns the datum of a node * getLeft() // returns the left subtree * getRight() // returns the right subtree Modifiers(0) // But will add some soon enough in other parts of this mini-project Utility (2) * printTree() // prints data in tree using infix (inorder) notation * toString() // make sure the node can be an argument to System.out.print methods 2. Add the following methods to your BST class: * depth() // returns the depth of the tree--one node counts a as depth of 1, not 0 * insert(T datum) * EXTRA CREDIT: delete(T datum) // find datum in the binary search tree; if found, delete node, // but remember, this must remain a BST after deletion 3. Create a binary search tree by inserting the numbers 1 ... 10000 in random order. * Try to predict the average depth of such a tree * Run your program a few times, record the depths of the trees, and compare your prediction to the result 4. Algorithm analysis. * What is the worst case order of growth for finding a datum in a binary search tree? * What is the best case? * What do you think thecase order of growth is? (In other words, if a tree were created as in (3), above, in random order, what would you expect the typical order of growth for searching to be?) * What is the order of growth to insert an element in the tree? * What is the order of growth to print the tree? * EXTRA CREDIT: What is the order of growth to delete an element?average