Thread: binarysearchtree traversing

Hi, I'm trying to figure out how to do this contains method. everything that's in the method is my code. My thinking is: start at root and go in Inorder traversal and use .equals(). Should I even do that? is there a way I can compare the data, since BST will have lower value to left and higher in right child? I'm lost.

/**
Searches for a given element in the binary search tree
@param someElement element to be searched
@return true - if someElement is found in the tree; false otherwise
*/
// Complexity: O(h) - where h is the height of the tree. In the worst case it could be O(n).  But on average
// we can expect a complexity of O(log n)
public boolean contains( E someElement) {
 
	Node node1 = root;
	if(root == someElement)
		return true;
 
 
	if(node1.left != null){
		boolean result = someElement.equals(node1.left);
		if(result == false){
			contains((E) node1);
 
		}
 
	}
}

done! thanks

Originally Posted by Norm

Is someElement a Node or contained in a Node?

I'm pretty sure it's contained in a node.

Your best bet might be to use a recursive call on both child nodes.

ok so this is what i have so far. does it make sense??

	Node node1 = root;
	boolean result = false;
 
	if(root == someElement)
		return true;
	//go through left
	if(node1.left != null){
		result = someElement.equals(node1.left);
		if(result == false){
			contains((E) node1.left);
		}
	}
	//go through right
	if(node1.right != null){
		result = someElement.equals(node1.right);
		if(result == false){
			contains((E) node1.right);
		}
return result;
	}

Originally Posted by Norm

Not if someElement is not a Node. The code needs to compare against the contents of a Node.

Can you make a complete program for testing this method? Build a simple tree and call the method. Add some println() statements for debugging and execute it to see what happens.

if I cast node1 as <E> will it make a difference?