# a BST question

• 05-12-2011, 11:56 AM
smacker
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 ?
• 05-12-2011, 12:41 PM
JosAH
Quote:

Originally Posted by smacker
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:

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:

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
• 05-12-2011, 12:57 PM
smacker
duh , yea man no wonder it didn't stop
thanks a lot for clarifying it
• 05-12-2011, 01:03 PM
smacker
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 )
• 05-12-2011, 01:16 PM
JosAH
Quote:

Originally Posted by smacker
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
• 05-12-2011, 01:28 PM
smacker
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 .
• 05-12-2011, 01:30 PM
smacker
bleeeh just figured it out...
it was missing a.data = min(data.left)
:)
• 05-12-2011, 01:55 PM
JosAH
Quote:

Originally Posted by smacker
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
• 05-12-2011, 02:34 PM
smacker
oh i see , now it works without running over the tree

thanks a lot jos !