Member Avatar for Syrne

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!

  • 2 Contributors
  • 2 Replies
  • 266 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by Syrne

Dani AI

Generated

Short answer: use a Comparator (or require E to be Comparable) and perform a pruned in‑order traversal. As pointed out, generics don’t support > so comparisons must go through compare/compareTo. The recursive idea is simple: visit left, decide whether to include the current node, then visit right — but skip right subtrees when the current node is already >= the before value.

Recursion logic (step‑by‑step)

  • Base case: node == null → return.
  • Compare node.data with before via your Comparator.
  • If node.data < before: recurse left, add node.data to the result set, then recurse right (right may contain more values < before but will be checked).
  • If node.data >= before: recurse only left (everything in right will be ≥ node.data, so none can be < before).

A compact helper (adapt to your Node/field names):

private void collectHead(Node node, E before,
                         Comparator<? super E> comp,
                         SortedSet<E> out) {
    if (node == null) return;
    int cmp = comp.compare(node.data, before);
    if (cmp < 0) {
        collectHead(node.left, before, comp, out);
        out.add(node.data);
        collectHead(node.right, before, comp, out);
    } else {
        collectHead(node.left, before, comp, out);
    }
}

Call this from your public headSet after creating an empty result set and obtaining a Comparator (use the tree’s Comparator if provided, otherwise cast to Comparable). Return an empty set when the tree is empty (avoid returning null).

Troubleshooting and cautions

  • Ensure your Comparator/compareTo is consistent with equals.
  • Handle null before explicitly (throw NPE or define behavior).
  • Very deep, unbalanced trees can cause StackOverflow; consider an explicit stack if that’s a concern.
  • This implementation returns a copy; Java’s SortedSet.headSet normally returns a view — decide which semantics you need.

Recommended Answers

All 2 Replies

Member Avatar for JamesCherrill

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

Member Avatar for Syrne

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 by Syrne
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.