aspose file tools*
The moose likes Beginning Java and the fly likes Java binary search tree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Java binary search tree" Watch "Java binary search tree" New topic
Author

Java binary search tree

Jacky Kim
Greenhorn

Joined: Oct 17, 2009
Posts: 1
Welcome!
I have a recursive public static method named less that takes a tree node (an original binary tree, not really a search tree) and a int parameter that returns if all the values in the tree are less than the integer. The method has to be static. So, a method I wrote is like this:

is this method right?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39409
    
  28
Welcome to JavaRanch

Never write
if ( boo ) return true; which is regarded as poor style. Write return boo;

That might terminate your method, so put all your tests into one statement. Join it together with &&s or ||s but remember the precedences and whether you need (). And remember the difference between &&/|| and &/| when used on boolean values.

return t == null || . . . < v && less( . . . );

Note if the value is < v, then there is no need to check the left branch; you are simply looking for the largest value in the whole tree. Imagine what would happen with a 1000000-member tree! Using "right" only would require log21000000 = approx 20 comparisons on average.
I have kept the boolean terms in the same order you had. You already obviously know you must test for nullity when you reach the "leaf". You can get rid of two of the three returns in your method like this. You can use the three parts in different orders and it will still work. Or you can get the order wrong and suffer a NullPointerException
Remember what will happen if you pass null as an argument.
And good luck with it.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

Campbell Ritchie wrote:Never write
if ( boo ) return true; which is regarded as poor style. Write return boo;

That's not the same. "return boo;" is the same as "if (boo) return true; else return false;". Since the "return false;" is missing, the statement is quite valid indeed.

That might terminate your method, so put all your tests into one statement.
Although it will have the same effect, it may be easier to read the method if you don't do this. In fact, the only thing I would definitely have changed in the above is the removal of the else:

Note if the value is < v, then there is no need to check the left branch;

The current code already does that check, doesn't it? If t.value >= v false is returned.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39409
    
  28
Rob Prime wrote: . . . That's not the same. "return boo;" is the same as "if (boo) return true; else return false;".
That is why I said it would terminate the method. I obviously wasn't clear. Sorry.
Note if the value is < v, then there is no need to check the left branch . . .
The current code already does that check, doesn't it? If t.value >= v false is returned.
But the original code checked that t.value < v, then checked that t.left was less, then t.right. If value < v, then everything on the left will be < v too, assuming this tree is correctly sorted, so it will check the entire left half of the tree, returning true from everything before it even looks at the right half of the tree.

Of course if the tree isn't sorted (I was assuming a tree would be implicitly sorted) then a left check might be necessary.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

Campbell Ritchie wrote:assuming this tree is correctly sorted [...]

Of course if the tree isn't sorted (I was assuming a tree would be implicitly sorted) then a left check might be necessary.

Well, you know what they say about assumptions, right? It's the mother of all [insert nasty word]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39409
    
  28
Only one way to find out:

Jacky Kim: is your binary tree already sorted?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Java binary search tree