Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has TreeNode as nested class in Java.

Design the class, TreeNode to have following class variables: int key; // All keys are in the range 1 to 99 TreeNode leftChild; TreeNode rightChild;

boolean deleted; Your program method must have routines to do the following operations.

insert //Should insert a new element to a leaf node. If new element is a duplicate then do nothing. If the new element is previously deleted one, then do not add other copy just mark the previous deleted as valid now

delete //Should not remove the element from the tree. It should just mark the element as deleted.

findMin //Should return the minimum element, but if it is marked deleted return appropriate minimum

findMax //Should return the maximum element, but if it is marked deleted return appropriate maximum

contains //Should return true if a particular element is in the tree and is not marked as deleted

In order tree Traversal //Should print the in order traversal of the tree. Indicating with * symbol for elements that are marked deleted

Height ( returns the height of the tree) //Return the height of the tree, count all the elements even the ones that are marked as deleted

No Of nodes ( returns number of nodes + number of deleted nodes)

//Print size of the tree, count all the elements even the ones that are marked as deleted. And

also return the number of deleted elements.

You may have other routines that may be necessary. The program should prompt user with options to do one of the above routines.