Trying to fix issue with compareTo() method

Question

I've been working on a project to make a generic binary search tree, and the code is for the most part finished. However, this one part of the code isn't working, and I'm not sure how to fix it.

private Node<E> add ( E item, Node<E> root ) {

    if ( root == null ) {
        return new Node<E>(item);
    }
    if ( root.data == item ) {
        return root;
    }
    else if ( root.data.compareTo(item)< 0) {
        root.right =  add ( item, root.right );
    }
    else {
        root.left = add ( item, root.left);
    }
    return root;
}

The error occurs on the first "else if" statement, and the error message I get is that "class java.lang.String cannot be cast to class java.lang.Integer (java.lang.String and java.lang.Integer are in module java.base of loader 'bootstrap')." Outside of the provided code, I have integers and characters being taken as inputs to test that the binary tree works with multiple data types. I know compareTo() can work between characters and integers, it would compare the ascii value of the character against the integer. From there, the only thing I can think of to be causing this issue is the "root.data.compareTo(item)..." If I'm correct, and that is what's causing my issue, how would I be able to compare that specific instance of root.data to the item variable?

I am providing the entire code below, to show the different interactions between classes, objects, and methods.

package project4;

import java.util.Iterator;

public class BST<E extends Comparable<E>> extends Object implements Iterable<E>, Cloneable{
    public static void main(String args []){
        BST tree = new BST();
        tree.add("g");
        tree.add(5);
        tree.add(6);
        tree.add(2);
        tree.add(4);
        tree.add("h");
        System.out.println(tree.toStringTreeFormat() );
    }

// actual class definition

    private Node<E>  root;
    private E[] elements;
    
    public BST() {
        root = null;
    }
   /* 
    BST(E[] collection){
        if(collection == null) {
            throw new IllegalArgumentException("Can not provide a null argument");
        }
        else {
            
        }
    }
    */
    // add function
    /*
        public boolean add( int val ) {
            if (root == null ) {
                Node n = new Node (val) ;
                root = n;
                return true;
            }

            return add (val, root);

        }

        private boolean add (int val, Node n ) {

            //found duplicate
            if ( val == n.data) return false;


            if ( val < n.data ) { // go left
                if ( n.left == null ) {//attach it right here
                    Node current = new Node (val);
                    n.left = current;
                    return true;
                }
                else { // recurse to its left subtree
                    return add(val, n.left) ;
                }
            }
            else { // go right
                if ( n.right == null ) {//attach it right here
                    Node current = new Node (val);
                    n.right = current;
                    return true;
                }
                else { // recurse to its right subtree
                    return add(val, n.right) ;
                }

            }
        }
    */

    public boolean add ( E e ) {
        int oldSize = size();
        root  =  add( e, root );
        if (oldSize == size())
            return false;
        return true;
    }

    private Node<E> add ( E item, Node<E> root ) {

        if ( root == null ) {
            return new Node<E>(item);
        }
        if ( root.data == item ) {
            return root;
        }
        else if ( root.data.compareTo(item)< 0) {
            root.right =  add ( item, root.right );
        }
        else {
            root.left = add ( item, root.left);
        }
        return root;
    }

    // remove function



    private boolean found ;

    public boolean remove(E val)
    {
        found = false;
        root = recRemove(val, root);
        return found;
    }

    private Node<E> recRemove(E target, Node<E>  node)
    {
        if (node == null)
            found = false;
        else if (target.compareTo(node.data) < 0)
            node.left = recRemove(target, node.left);
        else if (target.compareTo(node.data) > 0)
            node.right = recRemove(target, node.right );
        else {
            node = removeNode(node);
            found = true;
        }
        return node;
    }

    private Node<E> removeNode(Node<E> node)
    {
        E data;

        if (node.left == null)
            return node.right ;
        else if (node.right  == null)
            return node.left;

        else {
            data = getPredecessor(node.left);
            node.data = data;
            node.left = recRemove(data, node.left);
            return node;
        }
    }

    private E getPredecessor(Node<E> subtree)
    {
        Node<E> temp = subtree;
        while (temp.right  != null)
            temp = temp.right ;
        return temp.data;
    }

    // check if a value is stored in the tree
    public boolean contains (E val ) {
        if (root == null)
            return false;
        Node<E> cur = root;

        do {
            E curVal = cur.data;

            if (val == curVal)  return true;
            if (val.compareTo(curVal) < 0) cur = cur.left;
            else cur = cur.right;

        } while (cur != null) ;

        return false;


    }

    // this should be stored in a data filed to improve performance
    // calculation is done just as an exercise
    public int size ( ) {
        return size(root);
    }
    private int size( Node<E> n ) {
        if (n == null ) return 0;
        return 1 + size(n.left) + size(n.right);
    }

    private static class Node<E>{

        E  data;
        Node<E>  left ;
        Node<E>  right ;

        Node( E data ) {
            this.data = data;
        }

        Node(E data, Node<E> l, Node<E> r ) {
            this.data = data;
            left = l;
            right = r;
        }

    }

    private void preOrderPrint(Node<E> tree, int level, StringBuilder output) {
        if (tree != null) {
            String spaces = "\n";
            if (level > 0) {
                for (int i = 0; i < level - 1; i++)
                    spaces += "   ";
                spaces += "|--";
            }
            output.append(spaces);
            output.append(tree.data);
            preOrderPrint(tree.left, level + 1, output);
            preOrderPrint(tree.right, level + 1, output);
        }
        // uncomment the part below to show "null children" in the output
        
        else {
            String spaces = "\n";
            if (level > 0) {
                for (int i = 0; i < level - 1; i++)
                    spaces += "   ";
                spaces += "|--";
            }
            output.append(spaces);
            output.append("null");
        }
        
    }


    public String toStringTreeFormat() {

        StringBuilder s = new StringBuilder();

        preOrderPrint(root, 0, s);
        return s.toString();
    }

    @Override
    public Iterator<E> iterator() {
        // TODO Auto-generated method stub
        return null;
    }

Answer 1

You can't use Comparable<T> to compare Integer and String instances, because Integer cannot be cast to a String or vice versa. This means that a Comparable<Integer> instance cannot be called with compareTo("abc"). The fact that you are using your BST<E> class as a "raw type" (see What is a raw type and why shouldn't we use it?) without using the generic type makes it even more complicated because it looks like it is working (because your add() method allows any type), but it doesn't (as you see by the exception).

If you want to add String and Integer instances to your BST class, you have to drop the generic type E and its restriction to extends Comparable<E> or change it to just Object. That way you can add any object to your BST class. But this also means that you have to provide your own compare method, which must compare two instances and return an ordering for them, specially when they have different types.

This is what the Comparator<T> interface is specifying. It is used to compare two instances with the compare(T, T) method. As an example, the TreeSet<T> class can work with an Comparator<T> instance in case the objects cannot be sorted by themself.

You can use the TreeSet approach and say "I want to use a BST and use that comparator to compare the objects". This means that you have to implement the Comparator<Object> interface in a new class, which compares Integer and String objects for you. You have to use the generic type Object since that is the common base class for Integer and String. The new class body will look like this:

public class ASCIIComparator implements Comparator<Object> {

    @Override
    public int compare(Object o1, Object o2) {
        
    }
}

The tricky part is obviously the compare() method since you have to check different situations like comparing two strings, two integers or one string and one integer. Also you have to check that no other types are used and throw an exception (which must be documented somewhere that it does throw an exception). That also means that you can't get around to convert your strings and integers to ASCII values, which you then can compare. But you can do that inside this compare() method, without affecting what you store in your BST class.

When you have such ASCIIComparator class, you can rewrite your BST class to work with any Comparator<T> instance. The class body should be rewritten like this:

public class BST<E> implements Iterable<E>, Cloneable {
    private final Comparator<E> comparator;

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

    // [...]
}

Then inside your add() method, you use the this.comparator instance to compare two instances and decide what to do like this:

// [...]
int order = this.comparator.compare(root.data, item);
if (order < 0) {
    // ...
} else {
    // ...
}
// [...]

The generic type E ensures, that the comparator given in the constructor call must also be of type Comparator<E>, so it must "fit" for the BST class. With that you can create a BST class with the ASCIIComparator like this:

    BST<Object> tree = new BST<Object>(new ASCIIComparator());
    tree.add("g"); // String is an Object
    tree.add(5);   // Integer is an Object (autoboxed)
    tree.add(6);
    tree.add(2);
    tree.add(4);
    tree.add("h");
    System.out.println(tree.toStringTreeFormat() );

Since the ASCIIComparator class is implementing the Comparator<Object> interface, your BST class have to use the generic type Object as well.