Results 1 to 4 of 4
 02212013, 10:41 PM #1Member
 Join Date
 Oct 2010
 Posts
 45
 Rep Power
 0
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
Java 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; }
Last edited by hoosierfan24; 02222013 at 06:22 AM. Reason: code update
 02222013, 01:48 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,005
 Blog Entries
 7
 Rep Power
 23
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:
Java 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); }
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 02222013, 10:02 PM #3Member
 Join Date
 Oct 2010
 Posts
 45
 Rep Power
 0
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
 02232013, 09:17 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,005
 Blog Entries
 7
 Rep Power
 23
Re: FindMin and Max in a BST after Lazy deletion
I have the stamina of a seal; I lie on the beach instead of running on it.
Similar Threads

Lazy Initialization
By onegcr in forum New To JavaReplies: 1Last Post: 08142007, 03:29 PM
Bookmarks