Best way to deal with some classes implementing comparable and some not in a Binary search tree

Question

I am looking for suggestions on how to handle some possible elements implementing comparable and some not.

I am currently trying to do it like this

class BinaryTree<E> { 
  private Comparator<E> comparator;
  public <T extends Comparable<E>>() BinaryTree() {
    comparator = (T a, T b) -> a.compareTo(b)
  }


  public BinaryTree(Comparator<E> comparator) { 
    this.comparator = comparator
  }
}

//rest of the class (add, remove etc)

And then the comparator variable is used. I cant get it to compile tho.

Answer 1

Just check and see if a comparator has been provided. If so, use it. Otherwise, presume that the objects implement it. The downside is that if the objects don't implement it you will get a runtime exception instead of a compiler error.

class BinaryTree<E> {

    private Comparator<E> comparator = null;

  
    public BinaryTree() {
    }
    
    public BinaryTree(Comparator<E> myComparator) {
          this.comparator = myComparator;
    }
    
    public void traverse() {
        if (comparator != null) {
            //use it
        } else {
            // compare Objects presuming they implement comparable.
        }
    }
}

Answer 2

Normally this use case is handled by casting. See TreeSet for example. One way to do it would be like this:

public BinaryTree() {
  this((e1, e2) -> ((Comparable<E>) e1).compareTo(e2));
}

Naturally, this will throw ClassCastException at runtime, if you try to add elements, which do not implement Comparable.

I would do it with a static factory method. Like this you can declare the type variable to be bound as a subclass of Comparable:

public class BinaryTree<E> {
  
  private Comparator<E> comparator;

  public static <T extends Comparable<T>> BinaryTree<T> fromComparable() {
    return new BinaryTree<>(Comparable::compareTo);
  }

  public BinaryTree(Comparator<E> comparator) { 
    this.comparator = comparator;
  }
}

The compiler now won't allow you to create a BinaryTree with non-comparable elements:

BinaryTree<Integer> tree1 = BinaryTree.fromComparable(); //compiles succesfully
BinaryTree<NonComparableClass> tree2 = BinaryTree.fromComparable(); //compilation error