using compareTo in Binary Search Tree program

Question

I've been working on this program for a few days now and I've implemented a few of the primary methods in my BinarySearchTree class such as insert and delete. Insert seemed to be working fine, but once I try to delete I kept getting errors. So after playing around with the code I wanted to test my compareTo methods. I created two new nodes and tried to compare them and I get this error:

Exception in thread "main" java.lang.ClassCastException: TreeNode cannot be cast to java.lang.Integer at java.lang.Integer.compareTo(Unknown Source) at TreeNode.compareTo(TreeNode.java:16) at BinarySearchTree.myComparision(BinarySearchTree.java:177) at main.main(main.java:14)

Here is my class for creating the nodes:

    public class TreeNode<T> implements Comparable
    {
        protected TreeNode<T> left, right;
        protected Object element;

    public TreeNode(Object obj)
    {
        element=obj;
        left=null;
        right=null;
    }

   public int compareTo(Object node)
   {
       return ((Comparable) this.element).compareTo(node);
   }

}

Am I doing the compareTo method all wrong? I would like to create trees that can handle integers and strings (seperatly of course)

Thanks for all help guys! I ended up getting it working, but the problems was that I miswrote the variables a bit so I ended up confusing myself. The object I was passing to the compareTo method was the element itself, not a TreeNode. In my other class I kept passing it a TreeNode and thats why it was messing up. Thanks again. — Scott Rogener
– Scott Rogener, Commented Nov 21, 2011 at 7:30

Óscar López · Accepted Answer · 2011-11-21 13:31:56Z

4

To be sure that the element indeed is a comparable object, and avoid all the casts, you could do something like this:

public class TreeNode<T extends Comparable<? super T>>
implements Comparable<TreeNode<T>> {

    protected TreeNode<T> left, right;
    protected T element;

    public TreeNode(T obj) {
        element = obj;
        left = null;
        right = null;
    }

    @Override
    public int compareTo(TreeNode<T> node) {
        return element.compareTo(node.element);
    }

}

For an usage example:

TreeNode<Integer> node1 = new TreeNode<Integer>(2);
TreeNode<Integer> node2 = new TreeNode<Integer>(3);
System.out.println(node1.compareTo(node2));

The above snippet prints -1 on the console.

edited Nov 21, 2011 at 13:31

answered Nov 21, 2011 at 2:05

Óscar López

237k38 gold badges321 silver badges391 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

newacct Over a year ago

for best results use the bound <T extends Comparable<? super T>>

Óscar López Over a year ago

@newacct just edited my post to include your suggestion, thanks!

LeleDumbo · Accepted Answer · 2011-11-21 01:52:48Z

2

compareTo method is applied against TreeNode (passed as node parameter), while you compare it with this.element, which is an Object contained in the TreeNode. Simply change to:

return ((Comparable) this.element).compareTo(node.getElement());

assuming you have getElement method.

answered Nov 21, 2011 at 1:52

LeleDumbo

9,3804 gold badges26 silver badges38 bronze badges

Comments

Brett Walker · Accepted Answer · 2011-11-21 01:54:44Z

2

Try

public <T> int compareTo(Object node) 
{ 
    return ((Comparable) this.element).compareTo( ( TreeNode<T> ) node ).element); 
}

edited Nov 21, 2011 at 1:54

answered Nov 21, 2011 at 1:49

Brett Walker

3,5921 gold badge20 silver badges37 bronze badges

Collectives™ on Stack Overflow

using compareTo in Binary Search Tree program

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related