Generics error.

[Brendon McCullum]

I'm implementing tree class for supporting various tree operations, and for storing data, I'm using TreeNode class. The structure is as follows:

/**
 * Tree class for supporting various tree operations.
 */
class Tree<T> {

	/**
	 * Root of the present tree.
	 */
	private TreeNode<T> root;
	
	/**
	 * Tree Node class for holding generic data types.
	 * Class is marked private as it's used internally.
	 * @param <T> Generic type.
	 */
	private static final class TreeNode<T> {
		private T data;
		private TreeNode<T> left;
		private TreeNode<T> right;
		
		// Constructor to initialize values.
		TreeNode (T value) {
			this.data = value;
		}
	}
	
	/**
	 * Method to find height of a given tree (recursively).
	 * @param root Root node of given tree
	 * @return Height of given tree.
	 */
	static final <T> int findHeight(TreeNode<T> root) {
		
		// In case tree is empty, or we've reached end of recursive call, just return 0.
		if (root == null) {
			return 0;
		} else {
			// Add 1 to present height, and find the max of left and right subtree heights.
			return Math.max(findHeight(root.left), findHeight(root.right)) + 1;
		}
	}
	
	/**
	 * Method to insert element to tree (recursively).
	 * This method doesn't allow duplicates to be added in tree.
	 * @param root Root node of given tree.
	 * @param value Value to be inserted.
	 * @throws NullPointerException if value is null.
	 */
	 final <T extends Comparable<T>> void insert(T value) throws NullPointerException {
		
		// Boundary condition.
		if (value == null) {
			throw new NullPointerException("Can't handle null values");
		} else if (root == null) {
			// If tree is empty, or it's end of recursive call.
			// Insert element here.
			root = new TreeNode<T>(value);          //ERROR 1 - Can't convert from Tree.TreeNode<T extends Comparable<T>> to Tree.TreeNode<T>
		} else {
			// Recur for left and right subtrees.
			if (value.compareTo(root.data) < 0) {     //ERROR 2 - Method compareTo not applicable for argument value.
				// Go to left.
				insert(root.left, value);
			} else {
				// Go to right.
				insert(root.right, value);
			}
		}
	}
}

I tried changing the above TreeNode class to accept only bounded parameter T using the following code to solve ERROR 1:

     private static final class TreeNode<T extends Comparable<T>> {

but error still exists. Also for second error, I already have a restriction on insert method to accept only values which are comparable, hence, I don't really understand the source of this error.
Is there any way I can eliminate these errors, without having to place a restriction on the class input to accept only Comparable values. I just want the insert method to have that restriction as it uses compareTo method.
Also, I won't mind any suggestions for a good generics tutorial, I have already read from Oracle documentation, but it still appears pretty much confusing to me. Thanks.

[Joe San]

Have a look here for some wonderful tutorials on Generics!

http://www.angelikalanger.com/GenericsFAQ/FAQSections/Features.html

[Joe San]

What happens if you try implementing the Comparable on your TreeNode?

private static final class TreeNode<T extends Comparable<T>> implements Comparable<T>

[Brendon McCullum]

Hi Joe, after a little bit more googling, I was able to solve both problems. But a code review for below code would certainly help:

/**
 * Tree class for supporting various tree operations.
 */
class Tree<T extends Comparable<T>> {

	/**
	 * Root of the present tree.
	 */
	private TreeNode<?> root;
	
	/**
	 * Tree Node class for holding generic data types.
	 * Class is marked private as it's used internally.
	 * @param <T> Generic type.
	 */
	private static final class TreeNode<T extends Comparable<T>> {
		private T data;
		private TreeNode<T> left;
		private TreeNode<T> right;
		
		// Constructor to initialize values.
		TreeNode (T value) {
			this.data = value;
		}
	}
	
	/**
	 * Method to find height of a given tree (recursively).
	 * @return Height of given tree.
	 */
	 final <T> int findHeight() {
		 return findHeight(root);
	}
	 
	 /**
	  * Helper method to find height of given tree.
	  * @param root Root of given tree.
	  * @return Height of given tree.
	  */
	 private final <T extends Comparable<T>> int findHeight(TreeNode<T> root) {
			
		// In case tree is empty, or we've reached end of recursive call, just return 0.
		if (root == null) {
			return 0;
		} else {
			// Add 1 to present height, and find the max of left and right subtree heights.
			return Math.max(findHeight(root.left), findHeight(root.right)) + 1;
		}
	}
	
	/**
	 * Method to insert element to tree.
	 * @param value Value to be inserted.
	 * @throws NullPointerException if value is null.
	 */
	 @SuppressWarnings("unchecked")
	final <T extends Comparable<T>> void insert(T value) throws NullPointerException {
		
		 if (value == null) {
				throw new NullPointerException("Can't handle null values");
		 }
		 // Return root of the updated tree.
		 this.root = insertNode((TreeNode<T>) root, value);
		
	}
	 
	/**
	 * Method to insert element to tree (recursively). 
	 * This method doesn't allow duplicates to be added in tree.
	 * @param root Root node of given tree.
	 * @param value Value to be inserted.
	 * @return root of updated tree.
	 */
	 private final <T extends Comparable<T>> TreeNode<T> insertNode(TreeNode<T> root, T value) {
			
		// Boundary condition.
		if (root == null) {
			// If tree is empty, or it's end of recursive call.
			// Insert element here.
			root = new TreeNode<T>(value);
			
			// If tree's root node needs to be updated.
			if (this.root == null) {
				this.root = root;
			}
		} else {
			// Recur for left and right subtrees.
			if (value.compareTo(root.data) < 0) {
				// Go to left.
				root.left = insertNode(root.left, value);
			} else {
				// Go to right.
				root.right = insertNode(root.right, value);
			}
		}
		return root;
	}
}

/**
 * Test class for testing Tree operations.
 */
class Test {
	
	public static void main(String[] args) {
		Tree<Integer> tree = new Tree<Integer>();
		
		tree.insert(5);
		tree.insert(4);
		tree.insert(3);
		System.out.println("Height: " + tree.findHeight());
	}
}

Also, thanks for the link. I'll check it out.

[Stephan van Hulst]

Hi Brendon, here for the nitpicking again :P

- You should make your class declaration class Tree<T extends Comparable<? super T>>. The reason for this is that if you have a class that knows how to compare its instances, you can also create Trees of its subclasses. Let's say you have a class Fruit implements Comparable<Fruit>, and a class Pear extends Fruit. With your old class header, you won't be able to create a Tree<Pear>, because Pear does not extend Comparable<Pear>.

- Your root node should have the same type parameter as your tree: private TreeNode<T>.

- A TreeNode intrinsically belongs to a specific Tree. Don't make the class static. That way, you can even navigate back to the root from any node with Tree.this.root.

- The findHeight() methods have a type parameter. They don't need one, because they're not concerned with any element types to find the height of a tree.

- Your recursive findHeight() method doesn't use context (it only operates on the passed argument) so it can be static.

- The insert() and insertNode() methods don't need type parameters. They use the same type arguments as the Tree class. This will likely solve your unchecked problems (in combination with using a properly typed root).

- Your Tree class is not final, but you do define a bunch of final methods on it. It looks like you are designing for inheritance. You should consider overriding clone() to facilitate sub-classes that might want to implement Cloneable, you should consider implementing equals() and hashCode() and make them final, or specify what they do in a method stub with a contract. You're also not allowing sub-classes the opportunity to define more efficient implementations of findHeight() or insertNode().

[Stephan van Hulst]

Personally I wouldn't bind every Tree to a Comparable type. Instead, I would do something like this:

class BinaryTree<T> {

  Node root() {}

  Node createNode() {}

  final class Node {

    T key() {}

    Node left() {}

    Node right() {}
  }
}

class BinarySearchTree<T extends Comparable<? super T>> extends BinaryTree<T> {
  //
}