You are to develop a simple Binary Search Tree ADT and run it against a test program. Avoid the temptation of finding code online. I am aware of all the available solutions and will be looking closely at your code. You do not need to balance your tree. Basic Level (for a maximum grade of 85%): Develop the BST as a class that uses doubles as keys and Strings as values. Advanced Level (for a maximum grade of 100%): Develop the BST as a generic class that uses any objects as keys and values. Remember that a BST is a proper Binary Tree with the following property: Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v. We have key(u) Page < 2 > of 4 ZOOM " String toString(): Convert the BST to a hierarchical, indented String, as shown in the output below. Notice that I have also included a String toString(int level) in the Node class to help implement this hierarchy. Advanced Level: The complete design of the generic BST class is shown below. You will need to create the inner class Node. Refer to the Basic Level description above for a definition of the methods. BST -root: Node -size: int +BST() +insert(key: K, value: V): void +find(key: K): V -find(key: K, node n): V +delete(key: K): V +toString(): String +size(): int Node -key: K -value: V -left: Node -right: Node +Node(k: K, v: V) +getKey(): K +getValue(): V +getLeft(): Node +getRight(): Node +setLeft(n: Node): void +setRight(n: Node): void. +toString(): String +toString(level: int): String With either solution, when your implementation is complete, run it with the test driver BSTTest.java (provided). Review the results to make sure that your BST ADT is working correctly. The expected output is included in the file BSTExpected Output.txt and portions are shown below. Your output must include your name. 2. Notes You must use the test driver code found with this assignment: BSTTest.java. You should not modify BSTTest.java except to add your name. Turn in only your source files: BST.java and BSTTest.java. If you have created other classes as part of the solution, you need to turn those in as well. Make sure your class is not in a package (that is, it is in the default package). We normally must be careful when comparing double values. However, for the purposes of this assignment, you can assume that d1 == d2 will work for matching double keys. For the generic solution (Advanced level), you can assume that keys are Comparable. You will need to download the file words.txt and put it at the Project level within Eclipse. 3. Required Main Class BSTTest, provided 4. Required Input Not applicable + K Page < 3 > of 4 ZOOM 5. Required Output Your output should look like the following. The complete output is too long to include here, so I have removed selected lines (shown as ...). The complete output is available in BSTExpected Output.txt for comparison purposes. The Large Tree is random so your tree will not match mine. BST Test Program Your Name 1) Building a Tree ======================== Initially: null Insert (3.0, A): (k=3.00, v=A) null null Insert (4.0, E) (k=3.00, v=A) (k=2.00, v=C) null null (k=5.00, v=B) (k=4.00, v=E) null null (k=6.00, v=D) null null 2) Finding Elements ============ b1.find(2.0): C 3) Deleting Elements Delete (1.0) Left child, leaf: A (k=6.00, v=E) (k=3.00, v=H) (k=2.00, v=F) null null (k=5.00, v=C) (k=4.00, v=G) null null null (k=9.00, v=I) (k=7.00, v=J) null (k=8.00, v=B) null null (k=10.00, v=D) null (k=11.00, v=K) null null Delete (5.0) Has left child, internal: C (k=6.00, v=E) (k=3.00, v=H) (k=2.00, v=F) Page 3 + K null null (k=4.00, v=G) null null (k=9.00, v=I) (k=7.00, v=J) null null (k=10.00, v=D) null (k-11.00, v=K) null null Delete (6.0) Has two children, internal: E (k=7.00, v=J) (k=3.00, v=H) (k=2.00, v=F) null null (k=4.00, v=G) null null (k=9.00, v=I) null (k=11.00, v=K) null null 4) A Large Tree ======================== First 10: Size is now 10 Remaining Elements: Size is now 100000 Page < 4 of 4 ZOOM + K