java polymorphic binary search tree

How can I implement a polymorphic binary search tree (that makes use of EmptyTree and NonEmptyTree) without using downcasting or class checkin开发者_高级运维g?

Create a common interface such as:

interface TreeNode<K, V> {
   TreeNode<K, V> find(K key)
}

Then provide classes that implement the common interface:

class EmptyTree<K, V> implements TreeNode<K, V> {
   public TreeNode<K, V> find(K key) {
      // ...
   }
}

class NonEmptyTree<K, V> implements TreeNode<K, V> {
   public TreeNode<K, V> find(K searchKey) {
      // ...
   }
}

Your implementation for the EmptyTree will always indicate a failure in searching for the item (whether by returning null or by throwing an exception), while your implementation of NonEmptyTree will either return itself (if the provided search key matches) or delegate to the left or right subtrees. Because the left or right subtree will always exist (it will either be a NonEmptyTree or an EmptyTree), the "NonEmptyTree" class can simply refer to its children via the common interface and rely on the fact that the runtime type will do the right thing (thus it is not necessary to do any casting or type checking of the children in the implementation of the algorithm).

The only place where you need to know the runtime type is when you construct the children.