# idont understand why i get this resolt

alex lotel
Ranch Hand
Posts: 191
ihave built all the functions for the binary tree

i built a search method

and it says that there is no such object
i cant understand why???
[code]

public class main {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
btree t=new btree();
int x=7;

t.insert(x);
t.insert(x);
t.insert(x);

System.out.println(t.find(x));
}

}

public class bnode {

private bnode left;
private bnode right;
private Object data;

bnode(Object data)
{
this.data=data;
left=null;
right=null;

}
public void insert(Object x)
{
double i;
i=Math.random();
if (i>=0.5)
{
if (right==null){
this.right=new bnode(x);
}
else
{
right.insert(x);
}

}
if (i<0.5){
if (left==null){
this.left=new bnode(x);
}
else
{
left.insert(x);
}
}
}
public boolean find(Object x){

if (this.data.equals(x)) {
return true;

}
else
{
if (right!=null){
right.find(x);
}

if (left!=null){
left.find(x);
}
}
return false;
}
}

public class btree {
bnode root;

btree()
{
root=null;
}

public void insert(Object x)
{
if (root==null){
root=new bnode(x);
}
else
{
root.insert(x);
}
}

public boolean find(Object x)
{

if (root.equals(x)){
return true;
}
else
{
root.find(x);

}

return false;
}
}

[/code

Joanne Neal
Rancher
Posts: 3742
16
When you do find a match, you are not allowing this result to return up your recursive tree. You need to check the result of the call to right.find() and, only if it is false, should you call left.find(). If right.find returns true, you should return true straight away, otherwise you should return the result of left.find().

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
Well, at first glance, I see three categories of major problems here. First of all, sometimes you say something like "if (node.equals(x))" when in fact you mean "if (node.x.equals(x))". I think the best way to deal with this is just not to use equals() -- instead, give bnode a "contains" method, which makes the intent clearer, and then perhaps have contains() throw an exception if called with a bnode as an argument -- this will let you find programming problems quickly.

The second kind of problem is that you call functions recursively, but ignore the results. Your find() method will call find() on each of its subtrees, ignore their return values, then return false unconditionally. find() has to check whether the recursive call(s) succeed and if so, return true!

Thirdly, this is a pretty crazy tree in that it stores things randomly in one subtree or another. The performance of find() is therefore linear in the number of items in the tree, instead of logarithmic, since the tree has no idea where to find an object! The left/right decision should be based on something repeatable -- whether the return value of x.hashCode() is even or odd, for example.

Ravikanth kolli
Ranch Hand
Posts: 179
the main problem occurs in the find method of the btree. The search is actually implemented at the bnode level and "find" in the bnode searches the entire tree for the node, and thus returns a value.
It would be sufficient to call bnode find method in btree find method and return that value and that would work.

The actual problem here is that the elements are added into the B Tree but there is a simple logical error in the implementation.

Thanks hope this helps

alex lotel
Ranch Hand
Posts: 191
what simple logical error???

i have written a search function than when it finds the object it returns true and there the method stops

if it wont find anything it will return false in the end

what the problem with that???

in this case my object is in the root
so in the first IF in the btree class
it was supposed to return true

what is the error??

Ravikanth kolli
Ranch Hand
Posts: 179
The problems are the same identified by Ernest.

In line
if (root.equals(x)){
a comparision is being made between the bnode and an object. which can never be equal. The point is that bnode contains an object of type "data" that should be used for comparing.

So it should be something like

And also

The else part calls the method find from bnode which returns "true" if the element is present in the complete tree.
The error here is that you are not taking care of the value returned from the find method of bnode. So the above code just returns false if the element is not present in the root.
if you had something like return root.find(x); then it would have worked.

alex lotel
Ranch Hand
Posts: 191
so i need to change it like that??

Ravikanth kolli
Ranch Hand
Posts: 179
just a call to find method of bnode is sufficient

So you should be changing the "find method" of btree something like

this would call the find method of bnode which searches the complete list of elements in the tree and returns true if it finds the element or false if it doesnot

Rob Spoor
Sheriff
Posts: 20661
65
Technically the following is sufficient, since bnode.find(Object) already checks its own object:

Or shorter:

using the ternary operator.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Or:

[ March 04, 2008: Message edited by: Jim Yingst ]

alex lotel
Ranch Hand
Posts: 191
// return false here will not compile since this code will never be reached!

why it wont be reached
is it because bnode will give you all the options??
??
[ March 04, 2008: Message edited by: donaldth smithts ]

Campbell Ritchie
Sheriff
Posts: 50175
79
Originally posted by donaldth smithts:
why it wont be reached
is it because bnode will give you all the options??
??[ March 04, 2008: Message edited by: donaldth smithts ]
No, but because the rpeceding code has a "return" in an "else" block. Follow the execution with pencil and paper and see what happens should the "if" condition NOT be fulfilled. You get the "else." Whatever follows the "return" cannot ever be executed. Hence the compiler error.

Rob Spoor
Sheriff
Posts: 20661
65
The same goes for throwing exceptions, or looping without a break:
This is because this code can never ever be reached. Now of course the compiler could have ignored the code and give a warning, but Sun has decided to make it an error instead.