Page 1 of 1

Reputation:

# Cannot properly go through a tree recursively

Posted 11 December 2010 - 05:14 PM

Well I'll go straight to the point...
I'm trying to recursively move through a binary search tree. I'm not really sure what is wrong with my algorithm (and I'm also pretty new to recursion) but this is what I have:
```	public boolean contains(BTreeNode<T> node)
{
return containsItem(root, node);
}

private boolean containsItem(BTreeNode<T> current, BTreeNode<T> target)
{
boolean found = false;

if(current != null) {
if(current.equals(target))
{
found = true;
}
else{
if(current.getLeft() != null)
{
containsItem(current.getLeft(), target);
}
if(current.getRight() != null)
{
containsItem(current.getRight(), target);
}
}
}
else{
throw new EmptyCollectionException();
}
return found;
}
```

When i enter
```System.out.println(BST.contains(new BTreeNode(45)));
```

it returns false (45 IS an item in a Binary search tree called BST)
What am I doing wrong? Is there something wrong with my base case? Please give me some insight.

Is This A Good Question/Topic? 0

## Replies To: Cannot properly go through a tree recursively

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,163
• Joined: 27-December 08

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 05:24 PM

Your main problem is that you are ignoring the recursive calls and what they return. To be honest, it might be easier to just get rid of your boolean and use return statements instead. So if the current Node has the value, return true. Else if the recursive call to the left returns true, then return true. Same for the recursive call on the right. Finally, return false because you haven't returned true.

Reputation:

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:15 PM

macosxnerd101, on 11 December 2010 - 04:24 PM, said:

Your main problem is that you are ignoring the recursive calls and what they return. To be honest, it might be easier to just get rid of your boolean and use return statements instead. So if the current Node has the value, return true. Else if the recursive call to the left returns true, then return true. Same for the recursive call on the right. Finally, return false because you haven't returned true.

I'm not sure I understand 100% what you're saying here. But from what I understood I used to write this code:
```	private boolean containsItem(BTreeNode<T> current, BTreeNode<T> target)
{
if (current == null){
throw new EmptyCollectionException();
}
else if(current.equals(target))
{
return true;
}
else if (containsItem(current.getLeft(), target))
{
return true;
}
else if (containsItem(current.getRight(), target))
{
return true;
}
else
{
return false;
}
}
}
```
But this doesn't return false values, this throws the exception when the tree isn't empty. I'm confused even more now, help?!

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,163
• Joined: 27-December 08

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:20 PM

You should in your first contains(BTreeNode<T>) method check to see if your Collection is empty before invoking the overloaded contains() method so only the root Node will be checked for the Exception, not other childless Nodes. Otherwise, your revised method looks good.

### #5 Dogstopper

Reputation: 2950
• Posts: 11,217
• Joined: 15-July 08

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:20 PM

Well, I think you are throwing your exception incorrectly. If you have a tree like this:

```     1
/\
2  3
/ \  \
4   5  6

```

When you get to 4, 5, or 6, and those don't equal the target, it calls this:

else if (containsItem(current.getLeft(), target))

But, as you can see, 4 has null as a left element, which means that current == null and throws an exception as you have set up here:

if (current == null){ throw new EmptyCollectionException(); }

You need to not have that exception be thrown unless the ROOT node is null.

Reputation:

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:42 PM

macosxnerd101, on 11 December 2010 - 06:20 PM, said:

You should in your first contains(BTreeNode<T>) method check to see if your Collection is empty before invoking the overloaded contains() method so only the root Node will be checked for the Exception, not other childless Nodes. Otherwise, your revised method looks good.

Dogstopper, on 11 December 2010 - 06:20 PM, said:

Well, I think you are throwing your exception incorrectly. If you have a tree like this:

```     1
/\
2  3
/ \  \
4   5  6

```

When you get to 4, 5, or 6, and those don't equal the target, it calls this:

else if (containsItem(current.getLeft(), target))

But, as you can see, 4 has null as a left element, which means that current == null and throws an exception as you have set up here:

if (current == null){ throw new EmptyCollectionException(); }

You need to not have that exception be thrown unless the ROOT node is null.

that clarified things up alot for me. I got rid of the exception but now it returns null instead of true or false. This is what I changed my code to:
```	public boolean contains(BTreeNode<T> node)
{
if (root == null){
throw new EmptyCollectionException();
}
else{
return containsItem(root, node);
}
}

private boolean containsItem(BTreeNode<T> current, BTreeNode<T> target)
{
if(current.equals(target))
{
return true;
}
else if (containsItem(current.getLeft(), target))
{
return true;
}
else if (containsItem(current.getRight(), target))
{
return true;
}
else
{
return false;
}
}
```
And just to clarify I have this code in my main method:
```				BinarySearchTree BST = new BinarySearchTree();

try{
System.out.println(BST.contains(new BTreeNode(45)));
}
catch (Exception ex) {
System.out.println(ex.getMessage());
}
```

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,163
• Joined: 27-December 08

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:44 PM

You could check to make sure current != null before checking its value. So if current == null, then you would want to return false.

Reputation:

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:52 PM

macosxnerd101, on 11 December 2010 - 06:44 PM, said:

You could check to make sure current != null before checking its value. So if current == null, then you would want to return false.

But then it just returns false, while the node with the value 45 is clearly in the list.

### #9 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,163
• Joined: 27-December 08

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:59 PM

Post your revised code.

Reputation:

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 08:07 PM

macosxnerd101, on 11 December 2010 - 06:59 PM, said:

Post your revised code.

```	public boolean contains(BTreeNode<T> node)
{
if (root == null){
throw new EmptyCollectionException();
}
else{
return containsItem(root, node);
}
}

private boolean containsItem(BTreeNode<T> current, BTreeNode<T> target)
{
if(current == null)
{
return false;
}
else if(current.equals(target))
{
return true;
}
else if (containsItem(current.getLeft(), target))
{
return true;
}
else if (containsItem(current.getRight(), target))
{
return true;
}
else
{
return false;
}
}
```

and in my main method:
```		BinarySearchTree BST = new BinarySearchTree();

try{
System.out.println(BST.contains(new BTreeNode(05);)/>);
}
catch (Exception ex) {
System.out.println(ex.getMessage());
}
```
Dunno if this piece of information will help but I can successfully traverse the list recursively to print nodes in the list in infix, prefix, and postfix.

Reputation:

## Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 09:58 PM

Bump...