The task of this project is to implement in Java a binary search tree with lazy deletion. The BST class should contain a nested tree node class that is used to implement the BST. Specification The project must implement the following specification exactly, which includes identifier names, method signatures, the presence or absence of exceptional behavior, etc. Anything not clearly indicated by the UML class diagram (such as the access level of TreeNode fields) or explicitly stated in the natural language description is left up to your discretion. You may also add helper methods and additional fields as you see fit - in fact, you may find it necessary to do so! Structure LazyBinarySearch Tree +insert(key: int): boolean (throws IllegalArgumentException} +delete(key: int): boolean (throws IllegalArgumentException} +findMin(): int +findMax(): int +contains(key: int): boolean (throws IllegalArgumentException} +printAllWithDeleted (out: PrintStream): void +heightWithDeleted): int +sizeWithDeleted(): int TreeNode key: int leftChild: TreeNode rightChild: TreeNode deleted: boolean Note that the (+) relation in UML denotes nesting of scope, and not just composition of use. Behavior insert should insert a new element to a leaf node. If the new element would be a duplicate of a non-deleted element already in the tree, then insert should do nothing. However, if the new element is not a duplicate of a non-deleted element, but is a duplicate of a deleted element, then insert should "undelete" the deleted element in-place rather than physically inserting a new copy of the element. The return value of insert should indicate whether insert logically (as opposed to physically) inserted a new element. delete should not physically remove an element from the tree. Rather, it should mark the specified element as logically deleted. If the specified element is not in the tree or is already marked as deleted, then delete should do nothing. The return value of delete should indicate whether delete logically deleted an element. findMin should return the value of the minimum non-deleted element, or -1 if none exists. findMax should return the value of the maximum non-deleted element, or -1 if none exists. contains should return whether the given element both exists in the tree and is non-deleted. printAllWithDeleted should perform an in-order traversal of the tree and print the value of each element, including elements marked as deleted. However, elements that are marked as deleted should be preceded by a single asterisk. Every pair of adjacent elements should be separated by whitespace in the printing, but no whitespace should occur between an asterisk and the element with which it is associated. Leading and trailing whitespace is tolerable, but it will be ignored. printAllWithDeleted should print to its given argument, not to the program's standard output. (no additional messages should be printed, either) This method may assume that its argument is non-null and is in a valid state. An example of the output is as follows: 2 *5 30 45 47 50 *60 heightWithDeleted should return the height of the tree, including "deleted" elements. sizeWithDeleted should return the count of elements in the tree, including "deleted" ones. The valid set of keys is all integers in the range [1,99]. Every method that accepts a key argument should throw an IllegalArgumentException with an appropriate message iff the argument is invalid. No method specified herein should (intentionally) throw any other exception. In fact, no method (other than printAllWithDeleted) should even be able to result in any other exception for your program to be considered correct. Do not define any package (for this project, anyway). I.e. you should use the default package.