Cannot properly go through a tree recursively

[xecure]

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.

[xecure]

bump..

[~s.o.s~]

bump..

Bumps, and that too soon after posting your thread is rude. It's weekend in almost all parts of the world with Christmas just round the corner. You sure your homework/question is more important than people's personal life? Have some patience.

Anyways, back on topic, regarding your code, a few things come to mind:

• Are you properly overriding the equals() / hashCode() method of the BTreeNode class?
• Rather than checking for equality, you should compare the current node with the desired node to get the desired algorithm behaviour. From wikipedia:

  We begin by examining the root node. If the tree is null, the value we are searching for does not exist in the tree. Otherwise, if the value equals the root, the search is successful. If the value is less than the root, search the left subtree. Similarly, if it is greater than the root, search the right subtree. This process is repeated until the value is found or the indicated subtree is null. If the searched value is not found before a null subtree is reached, then the item must not be present in the tree.

A sample implementation might be:

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

Just implement the Comparable interface and you should be good to go.

[xecure]

I apologize for the untimely bump.

After implementing your code I dont get wrong true/false or null values. I get this: lab10.BTreeNode cannot be cast to java.lang.Comparable

this is the code I'm implementing:

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

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

[~s.o.s~]

As mentioned in my previous post, make sure that your BTreeNode class implements the Comparable<T> interface. Google for tutorials on how to implement it; here is the official one.

[xecure]

I've actually been instructed not to change the code in my BTreeNode class. What other ways of recursively traversing the tree can I use?

[~s.o.s~]

You sure? Can you post the code for your BTreeNode class?

[xecure]

BTreeNode class:

package lab10;

/**
 * <p>Title: BTreeNode.java</p>
 *
 * <p>Description: Defines a binary tree node class capable of 
 * storing an object reference and a reference to the left and right
 * subtrees. Accessors and mutators are defined for all instance variables.</p>
 * 
 * @author Darci Burdge
 */
public class BTreeNode<T>
{
  private T data;
  private BTreeNode<T> left, right;

  /**
   * default constructor --
   * creates an empty node; the left and right subtrees are empty.
   */
  public BTreeNode()
  {
    data = null;
    left = right = null;
  }

  /**
   * parameterized constructor --
   * creates a node storing the new item; the left and right subtrees 
   * are empty.
   */
  public BTreeNode(T newItem)
  {
    data = newItem;
    left = right = null;
  }

  /**
   * getItem --
   * returns the item stored in this node
   * @return a reference to the item in this node
   */
  public T getItem()
  {
    return data;
  }

  /**
   * getLeft --
   * returns the left subtree of this node
   * @return a reference to the left subtree
   */
  public BTreeNode<T> getLeft()
  {
    return left;
  }

  /**
   * getRight --
   * returns the right subtree of this node
   * @return a reference to the right subtree
   */
  public BTreeNode<T> getRight()
  {
    return right;
  }

  /**
   * setItem --
   * stores a new item in this node
   * @param newItem a reference to the new item to be stored
   */
  public void setItem(T newItem)
  {
    data = newItem;
  }

  /**
   * setLeft --
   * stores a new value as the left subtree
   * @param child a reference to the left subtree to be stored
   */
  public void setLeft(BTreeNode<T> child)
  {
    left = child;
  }

  /**
   * setRight --
   * stores a new value as the right subtree
   * @param child a reference to the right subtree to be stored
   */
  public void setRight(BTreeNode<T> child)
  {
    right = child;
  }

}

Was instructed by my professor.

[~s.o.s~]

That's not a very good implementation, without any logical overrides provided for the equals()/hashCode() method along with the instruction to not *touch* the class, the only option you have is to "inspect" the Node data. E.g. (untested):

private boolean containsItem(BTreeNode<T> current, BTreeNode<T> target) {
    if(current != null) {
        // assumptions:
        // 1. the data pushed into the tree implements logical ordering i.e. Comparable interface
        // 2. the data pushed is never null
        final int cmp = ((Comparable)current.getItem()).compareTo(target.getItem());
        if(cmp > 0) {
            return containsItem(current.getLeft(), target);
        } else if(cmp < 0) {
            return containsItem(current.getRight(), target);
        } else {
            return true;
        }
    } else {
        return false;
    }
}

[xecure]

That worked perfectly for me. My nodes are put on the list using the comparable interface, so i guess this method works.