10 Replies - 583 Views - Last Post: 11 December 2010 - 09:58 PM Rate Topic: -----

#1 Guest_hellskitchen*


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  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10669
  • View blog
  • Posts: 39,630
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Guest*


Reputation:

Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:15 PM

View Postmacosxnerd101, 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?!
Was This Post Helpful? 0

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10669
  • View blog
  • Posts: 39,630
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#5 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2874
  • View blog
  • Posts: 11,047
  • 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.
Was This Post Helpful? 0
  • +
  • -

#6 Guest_Guest*


Reputation:

Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:42 PM

View Postmacosxnerd101, 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. :)



View PostDogstopper, 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();
		
		BST.add(31);
		BST.add(45);
		BST.add(23);
		BST.add(59);
		BST.add(37);
		BST.add(50);
try{
			System.out.println(BST.contains(new BTreeNode(45)));
		}
		catch (Exception ex) {
			System.out.println(ex.getMessage());
		}

Was This Post Helpful? 0

#7 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10669
  • View blog
  • Posts: 39,630
  • 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.
Was This Post Helpful? 0
  • +
  • -

#8 Guest_Guest*


Reputation:

Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:52 PM

View Postmacosxnerd101, 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.
Was This Post Helpful? 0

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10669
  • View blog
  • Posts: 39,630
  • Joined: 27-December 08

Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 07:59 PM

Post your revised code.
Was This Post Helpful? 0
  • +
  • -

#10 Guest_Guest*


Reputation:

Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 08:07 PM

View Postmacosxnerd101, 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();
	
		BST.add(31);
		BST.add(45);
		BST.add(23);
		BST.add(59);
		BST.add(37);
		BST.add(50);
	
		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.
Was This Post Helpful? 0

#11 Guest_Guest*


Reputation:

Re: Cannot properly go through a tree recursively

Posted 11 December 2010 - 09:58 PM

Bump...
0_0
Was This Post Helpful? -1

Page 1 of 1