Implement BST using comparable or comparator

Question

I'm trying to create a generic BinarySearchTree<T> class. I want to provide two options (constructors),

1. Empty constructor for a generic class which implements Comparable<T> i.e. If Dog is a class which implements Comparable<Dog>, then:

   BinarySearchTree<Dog> bst = new BinarySearchTree<Dog>();

2. Pass a Comparator<T> for a generic class which need not have implemented Comparable<T>, i.e. If Dog is a class (did not implement Comparable<Dog>) and DogComp is a class which implements Comparator<Dog> then

   BinarySearchTree<Dog> bst = new BinarySearchTree<Dog>(new DogComp());

I have a Comparator field in my BinarySearchTree class. For empty consrtuctor, I will create new comparator. If comparator is passed, I will simply assign it to that comparator field.

How should I declare class and constructors?

Answer 1

I would like to improve on bot's answer:

Make the BinarySearchTree class abstract, with an abstract compare method. Two inner static concrete classes can then implement both schemes. Instead of a constructor, provide two construction methods like:

public static <E> BinarySearchTree<E> create(Comparator<? super E> comp) {
    return new ComparatorSearchTree(comp);
}

public static <E extends Comparable<E>> BinarySearchTree<E> create() {
    return new ComparableSearchTree();
}

This way the rest of the class can just use your compare(one, other) method without caring about whether the result is from a comparator or the natural element order.

You may have noticed that I specified comp as Comparator<? super E>. This means that the comparator is contravariant. This makes your search tree more flexible, because this way you can put in any comparator that is able to compare E objects, even if the comparator only compares F objects where F is a superclass of E.