Java recursive binary tree

Question

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. So, I would use a public class TN { public int value; public TN left, right; public TN(int v, TN l, TN r) {value = v; left = l; right = r;} } So, my method would look like this:

public static boolean less(TN s, int toFind){
if (s == null)
   return true;
else{ 
 if(s.value <= toFind)  
   return less(s.left, toFind) && less(s.right, toFind);  // right here do I return true? or do I have to somehow recall recursively
 else  
   return false; 
}

I was wondering if that was right or am I missing something??? Do I have to return true and false??

Answer 1

First, if (s = null) should be if (s == null) as you are doing a comparison, not setting the value of s to null.

The statement return less(null, toFind); keeps calling your method - you'll overflow your stack.

Answer 2

return less(s, toFind);

should be:

return less(s.left, toFind) && less(s.right, toFind);

I don't know why the function is static.

As mentioned before, your first part should just be:

if (s == null) return true;

(EDIT: This will let you get a true result when all nodes meet the condition. You have an == in there that should be a <). EDIT: Ok, you've got a lot of problems than just those I mentioned. You need to logically step through your code.

You need to traverse your tree, so you'll need to call your function on your children nodes. Next, you need to return true as your default result. That way, when you reach a number greater than what you're looking for, you can return false immediately without traversing any of the children. I hope I've helped you enough with the logic for you to get through the rest of it yourself.

Answer 3

There are much more elegant, OO ways to write this. My recommendation would be to make less() a non-static member function of the TN class. That way, if the tree's root node is called root, you just call root.less(). Each call to less() will then call left.less() and right.less().

Since you posted example code that wouldn't even compile, I'm wondering if you're using an IDE, or even tried to compile your class using javac. I strongly recommend getting Eclipse, Netbeans, or another IDE if you're new to Java.

Answer 4

Notice how there's no way that your function could ever return true because every time you terminate the recursion, you're returning false? And the problem is in your first check. You say that "all the values in the tree are less than the integer." Well, in an empty tree, all the values (of which there are none) are indeed less than any integer, so you should return true in that case.

Also, while you say "less than", you're comparing for equality, so you're actually checking whether all the values are equal to the integer, not less than it.