Redo the binary search tree class to implement lazy deletion

Redo the binary search tree class to implement lazy deletion. Note carefully that this affects all of the routines. Especially challenging are findMin and findMax, which must now be done recursively. Based on this, describe any modifications that you would need to make to the BinaryNode itself, and then show the implementation for findMin. You don\'t actually have to give us a full working class, only a description of the modification plus the findMin code. (In Java)

Solution

* Internal method to find the smallest item in a subtree
*
* @param t the node that roots the subtree
* @return the node containing the smallest item
*/
private BinaryNode<E> findMin(BinaryNode<E> t) {
if(t == null) {
return null;
} else if(t.left == null) {
return t;
} else {
return findMin(t.left);
}
}

/**
* Internal method to find the largest item in a subtree
*
* @param t the node that roots the subtree
* @return the node containing the largest item
*/

or try this code

private BinaryNode<E> findMin(BinaryNode<E> t) {

if (t == null) return null;

BinaryNode<E> tmp= findMin(t.left);

if (tmp != null) return tmp;

if (!t.deleted) return t;

return findMin(t.right);
}

Modification Description: