a BST question

[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 ?

[JosAH]

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:

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:

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

[smacker]

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

[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 )

[JosAH]

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

[smacker]

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 .

[smacker]

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

[JosAH]

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

[smacker]

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

thanks a lot jos !