How do I properly use a generic implementation of a binary search tree

Question

I wrote a binary search tree & binary search node classes and I'm not so good with generics so I tried to do it with generics . Now whenever I create a binary tree of the class I wrote it's perfectly okay to set the parameter type to String for instance, but if I create my own type then It doesn't let me use it. I'll explain , here's my BinaryNode & BinaryTree class, as well as the type Name I created myself which is essentially a string but I just wanted to test it:

BinaryNode:

public class BinaryNode<T extends Comparable<T>> {
T data;
BinaryNode<T> left;
BinaryNode<T> right;


public BinaryNode (T data){
    this.data = data;
}
public BinaryNode (){
    this(null);
}

//insert

public void insert(T data){
    // if data is less than node's data , then if left is null insert , if not do the same for left
    if(this.data.compareTo(data) > 0){
        if(this.left == null){
            left =  new BinaryNode<>(data);
        }
        else {
            left.insert(data);
        }
    }
    // if data is greater than node's data , then if right is null insert , if not do the same for right
    else if(this.data.compareTo(data) < 0) {
        if (this.right == null) {
            right =  new BinaryNode<>(data);;
        }
        else{
            right.insert(data);
        }
    }
    // if it's equal to node's data do nothing as we do not allow duplicate values.
}

public void traverseInOrder(){
    if(this.left != null){
        left.traverseInOrder();
    }
    System.out.println(this.data);
    if(this.right != null){
        right.traverseInOrder();
    }
}

public BinaryNode getMin(){
    if(left !=null) {
       return left.getMin();
    }
    return this;
}
public BinaryNode getMax(){
    if(right !=null){
       return right.getMax();
    }
    return this;
}
public BinaryNode get(T data){

    if(this.data.compareTo(data) > 0){
        if(this.left == null) {
            return null;
        }
        return left.get(data);
    }
    if(this.data.compareTo(data) < 0){
        if(this.right == null){
            return null;
        }
        return right.get(data);
    }
    return this;
}

@Override
public String toString() {
    return "data = " + data ;
}
}

BinaryTree:

public class BinaryTree<T extends Comparable<T>> {
BinaryNode<T> root;

public BinaryTree(T data){
    root = new BinaryNode<T>(data);
}
public BinaryTree(){
    root = null;
}

public void insert(T data){
    if(root == null){
        root = new BinaryNode<T>(data);
    }
    else{
        root.insert(data);
    }
}

public void traverseInOrder(){
    if(root == null){
        return;
    }
    root.traverseInOrder();
}

public BinaryNode getMin(){
    if(root == null){
        return null;
    }
    return root.getMin();
}

public BinaryNode getMax(){
    if(root == null){
        return null;
    }
    return root.getMax();
}

public BinaryNode get(T data){
    if(root == null){
        return null;
    }
    return root.get(data);

}


}

Name:

public class Name implements Comparable {
String name;


public Name(String name){
    this.name = name;
}
public Name(){
    this("");
}


@Override
public int compareTo(Object o) {
    if(!(o instanceof Name)) throw new IllegalArgumentException();
    String n1 = this.name.toLowerCase();
    String n2 = ((Name) o).name.toLowerCase();
    for(int i = 0; i< n1.length() && i< n2.length() ; i++ ){
        if(n1.charAt(i) > n2.charAt(i)) return 1;
        if(n2.charAt(i) > n1.charAt(i)) return -1;
    }
    if(n1.length() > n2.length()) return -1;
    if(n2.length() > n1.length()) return 1;

    return 0;
}
public String toString(){
    return name;
}
}

Now I can easily create a binary tree in Main like so:

BinaryTree<String> nametree = new BinaryTree<>();

But if I wanted to do something like:

BinaryTree<Name> nametree = new BinaryTree<>();

then I get a compilation error unless I go and change Comparable to Comparable in the BinaryNode and BinaryTree classes, and I feel I don't have a good grasp of generics so if anyone could please clarify what is wrong with doing what I did. and anything else that could help me make a better and correct use of generics that'd be great. Thanks in advance !

Your binary tree classes are fine. The problem is that `Name` implements the raw type of Comparable. A name should only be comparable to other names. Change `Name` to `implements Comparable`. — Michael, Jan 24 '19 at 13:14
By the way, you can probably notice from your `BinaryTree` implementation that that class is effectively completely redundant. In almost all methods it simply defers to the root node. If you take a step back, you will realise that every node can be considered a tree. Whether it is the root node is irrelevant because you can only traverse it top-to-bottom anyway — Michael, Jan 24 '19 at 13:18
do you have any suggestions on how to improve it? as well maybe as a remove method idea? — giorgioh, Jan 24 '19 at 15:00

score 2 · Answer 1 · answered Jan 24 '19 at 13:13

2

The problem might be that the Comparable interface requires a type when you are implementing it in Name.

Try setting the class definition of Name to be: public class Name implements Comparable<Name>

This answer gives a good explanation: Java- The meaning of <T extends Comparable<T>>?

answered Jan 24 '19 at 13:13

James Birch

321
1
7

That did solve it. thanks. By the way, how do I know if to add to the methods for example why do public BinaryNode get(){} and not public BinaryNode get(){} – giorgioh Jan 24 '19 at 13:24
Once you have written in the class declaration `public class BinaryNode` you don't need to use again when declaring methods. You can then use T as a type which you substitute when you create an object of BinaryNode. So, when you do BinaryNode all occurrences of T get substituted by String for that object. – James Birch Jan 24 '19 at 13:58

How do I properly use a generic implementation of a binary search tree

1 Answers1