Hi there, I'm attemtping to write my own version of the java "headSet" function which steps through a given tree set and returns all elements that are less than the function argument.

For example:

headSet(30) called for a set such as:

[2, 5, 7, 18, 22, 34, 50, 76]

should return

[2, 5, 7, 18, 22]

Where I'm having trouble is comparing the current node's data with the argument which happens to be an object of the set, here's the code so far:

public SortedSet<E> headSet(E before) {
        SortedSet<E> set = new SearchTreeSet<E>();
        Node check = root;
        if (isEmpty()) {
            return null;
        }

        while (check.right != null) {
            check = check.right;
        }

        while(check.left != null) {
            if(check.data > before) {
                remove(check.data);
                check = check.left;
            }

        }

        return set;    

    }

This line:

if(check.data > before)

returns an error saying

Bad operand types for binary operator '>'
first type: E
second type: E

where E is a type-variable:
E extends Object declared in class SearchTreeSet

Little confused here, how am I supposed to check the current node's data with the E object's data (the argument)?

Thank you for any and all help, if you need more information, let me know!

To compare two Objects you can either:
1. Implement the Comparable interface (which consists of a compareTo method) in the objects being compared, or
2. Write a Comparator that compares two arbitrary Objects
Both these interfaces are documented in the usual Java API documentation.

In this case it would be normal to define the SortedSet class to require objects that are Comparable, ie
class SortedSet<E extends Comparable>
then you can always use their compareTo methods to compare them

Thank you for the tip!

I implemented a comparator and it seems to be working, but I now have another question.

I realized that using an iterative method is very inefficient for this type of operation (tree traversal) and was told by my instructor to use recursion. I am very, well, sketchy on the logic behind recursion. I know what it means, but when I'm asked to write recursive functions to achieve a certain task, I end up getting very caught up on the logic. Here's what I have so far:

@Override
     public SortedSet<E> headSet(E before) {
     SortedSet<E> set = new SearchTreeSet<E>();
     headSet(root, before, set);
     return set;
     }

     private void headSet(Node n, E before, SortedSet<E> set) {
         n = root;
         int comp = myCompare(n.data, before);
     } 

I have yet to implement the "left and right" checks because I'm still thinking iteratively in that I want to use a collection of "if" statements rather than use recursive calls to the original function.

Would you mind giving some hints towards figuring out the logic for this recursive headSet function? Thank you!

Edited 4 Years Ago by Syrne

This article has been dead for over six months. Start a new discussion instead.