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. 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.

Source code for binary search: tree http://users.cis.fiu.edu/~weiss/dsaajava3/code/BinarySearchTree.java

Solution

We have to add a boolen variable deleted in each node and keep is false by default

private static class BinaryNode<AnyType>
{
// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}

BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
deleted = false;

}

AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
boolean deleted;
}

findMIn method

private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if (t == null) return null;

BinaryNode<E> tmp= findMin(t.left); // get minimum from the left node

if (tmp != null) return tmp; // if mimimum is not null return minimmum

if (!t.deleted) return t; // if minimum is null in left node and t is not deleted
// return t then

return findMin(t.right); // if t is deleted and minimum of left node of t is null, then search in right side

}