CODEWITHSUNDEEP
javabinary-search-tree
user1595515
user1595515

Reputation: 71

comparator and BST

im trying to create a method which allows me to check if a BST contains an item. this is what i have so far:

public boolean contains(Object item) {
    // YOUR CODE HERE

    //changes item to E so it can be used in the comparator
    E value1 = (E) item;

    if (root.value.equals(item)){
        return true;
    }

    comp.compare(value1,root.value);
    if(value1<root.value){
        if (left == null)
            return null;
        else
            return left.contains(item);
    }

    else if(item >= value){
        if (right == null)
            return null;
        else
            return right.contains(item);
    }
}

and these are my fields:

// Data fields
private BSTNode root;
private int count = 0;
private Comparator<E> comp;   // default comparator

/** Private class for the nodes.
 *  Has public fields so methods in BSTSet can access fields directly. 
 */
private class BSTNode {

    // Data fields

    public E value;
    public BSTNode left = null;
    public BSTNode right = null;

    // Constructor

    public BSTNode(E v) {
        value = v;
    }

}


public BSTSet() {
    comp = new ComparableComparator();      // Declared below
}

public BSTSet(Comparator <E> c) {
    comp = c;
}

my question is how do i fix my contains method so that it works. So far it gets to the line under comp.compare(value1.root.value)) and says that '<' cannot be used on two elements of type E. how do i fix this so that i can continue to run the comparator?

Upvotes: 1

Views: 618

Answers (2)

rai.skumar
rai.skumar

Reputation: 10675

You can have something like below:

public boolean containsItem(int i) {
    Node<Integer> t = new Node<Integer>(i);
    Node<Integer> r = (Node<Integer>) root;
    while(r != null){
        int cmp = t.compareTo((Node<Integer>) r);
        if(cmp == 0)
            return true;
        if(cmp >0 ) r = r.getRight();
        else r = r.getLeft();
    }
    return false;
}

You can have look at my blog to see how to implement compareTo method for BST.

Upvotes: 0

pcalcao
pcalcao

Reputation: 15988

Your comparator returns an int.

If this int is 0, than the value of both objects is the same, if it's less than 0, it's equivalente to your <, if it's more than 0, it's equivalent to your >.

You need to use the result of your comparator call to check if you should traverse the right or left sub-tree.

Also, please don't return null if the left/right branch is null, return false. That's the correct semantics of the algorithm, if there is no left branch and the value is smaller than the current root, than the item is not in the tree, hence, false.

Upvotes: 3

Related Questions