Results 1 to 9 of 9

Thread: a BST question

  1. #1
    smacker is offline Member
    Join Date
    Jan 2011
    Posts
    44
    Rep Power
    0

    Default a BST question

    i had to return the smallest in the tree so i did

    public Object minimum(){ // returns smallest in tree
    return min(this.root);
    }
    public Object min(BSTNode a){
    while (a.left!=null)
    min(a.left);
    return a.data;

    }

    the second one finds the smalllest and goes to return but then it jumps back to the loop for an endless loop
    any ideas anyone ?

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,519
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by smacker View Post
    i had to return the smallest in the tree so i did

    public Object minimum(){ // returns smallest in tree
    return min(this.root);
    }
    public Object min(BSTNode a){
    while (a.left!=null)
    min(a.left);
    return a.data;

    }

    the second one finds the smalllest and goes to return but then it jumps back to the loop for an endless loop
    any ideas anyone ?
    Make that:

    Java Code:
    public Object min(BSTNode a){
    		if (a.left!=null)
    			return min(a.left);
    		return  a.data;
    		
    	}
    This version just lets the recursion do the work; a purely iterative solution would run as follows:

    Java Code:
    public Object min(BSTNode a){
    		while (a.left!=null)
    			a= a.left;
    		return  a.data;
    		
    	}
    Your version tried to combine both methods (and fails as you have noticed).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    smacker is offline Member
    Join Date
    Jan 2011
    Posts
    44
    Rep Power
    0

    Default

    duh , yea man no wonder it didn't stop
    thanks a lot for clarifying it

  4. #4
    smacker is offline Member
    Join Date
    Jan 2011
    Posts
    44
    Rep Power
    0

    Default

    ok it's not looping but it's still going to the minimum
    goes to the return and then goes back to the recurrsion part
    in the end it returns the root of the tree (the one from the start )

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,519
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by smacker View Post
    ok it's not looping but it's still going to the minimum
    goes to the return and then goes back to the recurrsion part
    in the end it returns the root of the tree (the one from the start )
    Show your code; I bet it's not one of my versions ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    smacker is offline Member
    Join Date
    Jan 2011
    Posts
    44
    Rep Power
    0

    Default

    Java Code:
    public Object minimum(){  // returns smallest in tree
    		return min(this.root);
    	}
    	public Object min(BSTNode a){
    		if (a.left!=null)
    			min(a.left);
    		return  a.data;
    
    	}
    same as before only with an if , i add a print of the data it goes to the minimun but then goes back to the start and return the root .

  7. #7
    smacker is offline Member
    Join Date
    Jan 2011
    Posts
    44
    Rep Power
    0

    Default

    bleeeh just figured it out...
    it was missing a.data = min(data.left)
    :)

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,519
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by smacker View Post
    bleeeh just figured it out...
    it was missing a.data = min(data.left)
    :)
    Don't do that: it changes the entire path of leftmost nodes in your tree; have a close look at my recursive version again: just "return min(a.left);".

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    smacker is offline Member
    Join Date
    Jan 2011
    Posts
    44
    Rep Power
    0

    Default

    oh i see , now it works without running over the tree

    thanks a lot jos !

Similar Threads

  1. Question concerning question marks and colons
    By jim01 in forum New To Java
    Replies: 17
    Last Post: 01-14-2011, 12:05 AM
  2. Question mark colon operator question
    By orchid in forum Advanced Java
    Replies: 9
    Last Post: 12-19-2010, 08:49 AM
  3. question
    By berkeley in forum New To Java
    Replies: 5
    Last Post: 06-03-2010, 08:56 PM
  4. RMI question
    By alvandrood in forum New To Java
    Replies: 1
    Last Post: 09-14-2009, 12:36 PM
  5. JSP Question
    By maheshkumarjava in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 03-29-2008, 10:51 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •