Java Generics: compareTo and “capture#-of ?”

Question

I'm trying to write an implementation of a BinaryTree whose object can be of any type that implements Comparable. However, I realize that won't completely work. For example, A String and a Double wouldn't be able to be inserted into the same tree, even though they both implement Comparable.

So, I would like to know if it's possible to write the code such that the BinaryTree can be instantiated with any value whose type implements Comparable, but any ensuing elements added to the tree must all share the same supertype as the root's value.

Here's the code I have so far:

public class BinaryTree {

    private Node root;

    public BinaryTree() {

        this.root = null;
    }

    public Node lookup(Comparable<Object> value) {

        return lookup(this.root, value);
    }

    private Node lookup(Node node, Comparable<Object> value) {

        Node match = null;

        if (match != node) {

            if (value == node.value) {
                match = node;
            } else if (value.compareTo(node.value) < 0) {
                return lookup(node.left, value);
            } else {
                return lookup(node.right, value);
            }
        }

        return match;
    }

    public Node lookupNonRecursively(Comparable<Object> value) {

        return lookupNonRecursively(this.root, value);
    }

    private Node lookupNonRecursively(Node node, Comparable<Object> value) {

        Node match = null;

        if (match != node) {

            if (value == node.value) {
                match = node;
            } else {

                Node root = node;
                boolean found = false;

                while (!found && root != null) {

                    if (root.value.compareTo(value) < 0) {

                        if (root.left == null) {

                            root.left = match = new Node(value);
                            found = true;
                        } else {
                            root = root.left;
                        }
                    } else {
                        if (root.right == null) {

                            root.right = match = new Node(value);
                            found = true;
                        } else {
                            root = root.right;
                        }
                    }
                }
            }
        }

        return match;
    }

    public Node insert(Comparable<Object> value) {

        return insert(this.root, value);
    }

    private Node insert(Node node, Comparable<Object> value) {

        if (node == null) {
            node = new Node(value);
        } else {
            if (node.value.compareTo(value) <= 0) {
                insert(node.left, value);
            } else {
                insert(node.right, value);
            }
        }

        return node;
    }

    public Node insertNonRecursively(Comparable<Object> value) {

        return insertNonRecursively(this.root, value);
    }

    private Node insertNonRecursively(Node node, Comparable<Object> value) {

        if (node == null) {
            node = new Node(value);
        } else {

            Node root = node;
            boolean inserted = false;

            while (!inserted) {

                if (node.value.compareTo(root.value) < 0) {

                    if (root.left == null) {
                        root.left = node = new Node(value);
                        inserted = true;
                    } else {
                        root = root.left;
                    }
                } else {
                    if (root.right == null) {
                        root.right = node = new Node(value);
                        inserted = true;
                    } else {
                        root = root.right;
                    }
                }
            }
        }

        return node;
    }

    public static class Node {

        private Node left;
        private Node right;
        private Comparable<Object> value;

        public Node(Comparable<Object> value) {

            this.left = null;
            this.right = null;
            this.value = value;
        }
    }
}

And as a test, this will throw the error, The method insert(Comparable<Object>) in the type BinaryTree is not applicable for the arguments (Integer), if I try to run code like the following:

BinaryTree tree = new BinaryTree();
tree.insert(new Integer(1));

You can see I've implemented some different BinaryTree methods for this class, but the same rules would need to apply: any value passed into lookup() or insert() would also need to share the root's supertype. I have a feeling this is where some variant of <T extends Comparable<? super T>> is going to come into play, but my mind is just not figuring this one out.

Any ideas for how I might accomplish this?

As noted by @jp-jee, here's my solution (also with logic and other bugs fixed from untested first attempt), which works beautifully:

public class BinaryTree<T extends Comparable<T>> {

    private Node<T> root;

    public BinaryTree() {

        this.root = null;
    }

    public Node<T> lookup(T value) {

        return lookup(this.root, value);
    }

    private Node<T> lookup(Node<T> node, T value) {

        Node<T> match = null;

        if (match != node) {

            if (value.equals(node.value)) {
                match = node;
            } else if (value.compareTo(node.value) < 0) {
                return lookup(node.left, value);
            } else {
                return lookup(node.right, value);
            }
        }

        return match;
    }

    public Node<T> lookupNonRecursively(T value) {

        return lookupNonRecursively(this.root, value);
    }

    private Node<T> lookupNonRecursively(Node<T> node, T value) {

        Node<T> match = null;

        if (match != node && value != null) {

            if (value.equals(node.value)) {
                match = node;
            } else {

                Node<T> searchRoot = node;
                boolean found = false;

                while (!found && searchRoot != null) {

                    if (value.equals(searchRoot.value)) {
                        match = searchRoot;
                        found = true;
                    } else if (value.compareTo(searchRoot.value) < 0) {
                        searchRoot = searchRoot.left;
                    } else {
                        searchRoot = searchRoot.right;
                    }
                }
            }
        }

        return match;
    }

    public void insert(T value) {

        this.root = insert(this.root, value);
    }

    private Node<T> insert(Node<T> node, T value) {

        if (node == null) {
            node = new Node<T>(value);
        } else {
            if (value.compareTo(node.value) <= 0) {
                node.left = insert(node.left, value);
            } else {
                node.right = insert(node.right, value);
            }
        }

        return node;
    }

    public void insertNonRecursively(T value) {

        this.root = insertNonRecursively(this.root, value);
    }

    private Node<T> insertNonRecursively(Node<T> node, T value) {

        if (node == null) {
            node = new Node<T>(value);
        } else {

            Node<T> runner = node;
            boolean inserted = false;

            while (!inserted) {

                if (value.compareTo(runner.value) < 0) {

                    if (runner.left == null) {
                        runner.left = new Node<T>(value);
                        inserted = true;
                    } else {
                        runner = runner.left;
                    }
                } else {
                    if (runner.right == null) {
                        runner.right = new Node<T>(value);
                        inserted = true;
                    } else {
                        runner = runner.right;
                    }
                }
            }
        }

        return node;
    }

    public static class Node<T extends Comparable<T>> {

        private Node<T> left;
        private Node<T> right;
        private T value;

        public Node(T value) {

            this.left = null;
            this.right = null;
            this.value = value;
        }

        public Node<T> getLeft() {
            return left;
        }

        public Node<T> getRight() {
            return right;
        }

        public T getValue() {
            return value;
        }
    }
}

Answer 1

Make your Binary Tree generic like

public class BinaryTree<T extends Comparable<T>>{
   ...
}

Whenever creating a BinaryTree instance, specify the containied type:

new BinaryTree<MyClass>();

Where MyClass must implement Comparable<MyClass>, i.e. be comparable to Objects of the same class.

Your methods would read as (example):

 public Node lookup(T value) { ... }

The same applies for your Node class. Make it generic the same way.