# FindMin and Max in a BST after Lazy deletion

• 02-21-2013, 10:41 PM
hoosierfan24
FindMin and Max in a BST after Lazy deletion
Ive been working on this problem for two days now and cant seem to figure it out. I can do it by hand and know it has to be a recursive solution but I just cant get my recursion to work the way I want it to. When I say lazy deletion I mean the node is still
in the tree it just has a boolean called deleted that gets set to true if it is deleted

this is what I currently have

Code:

```private BinaryNode<E> findMin(BinaryNode<E> t)         {                 BinaryNode<E> r = t;                         if(t==null)                         return null;                 //found deleted node                 if(t.deleted && t.left!=null)                 {                                return findMin(t.left);                 }                 if(t.deleted && t.left==null)                 {                         if(t.right==null)                         {                                 return findMin(r);                         }                         return findMin(t.right);                 }                                 //found real node                 if(t.left ==null && !t.deleted)                 {                         return t;                 }                 if(t.left !=null && !t.deleted)                 {                         return findMin(t.left);                 }                                 return null;         }```
it returns the minimum though only ifW the actual minimum has not been lazily deleted from the tree. New update to the code allows it to get the minimum even if the smallest is deleted but the second smallest can only be one level higher than it
• 02-22-2013, 01:48 PM
JosAH
Re: FindMin and Max in a BST after Lazy deletion
I think you're over complicating things: you want to find the leftmost node that is not deleted; the following will do the job:

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); }```
kind regards,

Jos
• 02-22-2013, 10:02 PM
hoosierfan24
Re: FindMin and Max in a BST after Lazy deletion
The left most node might not necessarily be the smallest node in the tree tho. For example if the root of the bst is
77 and you insert 34, 7, 50, 28, 75, 20, 71, 15 and say you lazilly delete all the odd numbers your code would return 34 when the answer is actually 20
• 02-23-2013, 09:17 AM
JosAH
Re: FindMin and Max in a BST after Lazy deletion
Quote:

Originally Posted by hoosierfan24
The left most node might not necessarily be the smallest node in the tree tho. For example if the root of the bst is
77 and you insert 34, 7, 50, 28, 75, 20, 71, 15 and say you lazilly delete all the odd numbers your code would return 34 when the answer is actually 20

That's why my algorithm also checks the right subtree if a (root) node were deleted and nothing could be found in the left subtree.

kind regards,

Jos