Generic binary search tree implementation

Question

I use this interface for my BST node class:

public interface BinNode<E> {
 public E getValue();
 public void setValue(E value);
 public BinNode<E> getLeftChild();
 public BinNode<E> getRightChild();
 public boolean isLeaf();
}

My BSTNode is implemented as follows:

public class BinarySearchTreeNode<Key, E> implements BinNode<E> {
 private Key key;
 private E value;
 private BinarySearchTreeNode<Key, E> leftChild;
 private BinarySearchTreeNode<Key, E> rightChild;
 public BinarySearchTreeNode(Key key, E value,
 BinarySearchTreeNode<Key, E> leftChild,
 BinarySearchTreeNode<Key, E> rightChild) {
 this.key = key;
 this.value = value;
 this.leftChild = leftChild;
 this.rightChild = rightChild;
 }
 public Key getKey() {
 return this.key;
 }
 public void setKey(Key key) {
 this.key = key;
 }
 @Override
 public E getValue() {
 return this.value;
 }
 @Override
 public void setValue(E value) {
 this.value = value;
 }
 @Override
 public BinarySearchTreeNode<Key, E> getLeftChild() {
 return this.leftChild;
 }
 public void setLeftChild(BinarySearchTreeNode<Key, E> leftChild) {
 this.leftChild = leftChild;
 }
 @Override
 public BinarySearchTreeNode<Key, E> getRightChild() {
 return this.rightChild;
 }
 public void setRightChild(BinarySearchTreeNode<Key, E> rightChild) {
 this.rightChild = rightChild;
 }
 @Override
 public boolean isLeaf() {
 if (this.leftChild == null && this.rightChild == null) {
 return true;
 } else {
 return false;
 }
 }
}

And finally my binary search tree is implemented as:

public class BinarySearchTree<Key extends Comparable<? super Key>, E>
 implements Dictionary<Key, E> {
 private BinarySearchTreeNode<Key, E> rootNode;
 private int numberOfNodes;
 public BinarySearchTree() {
 this.rootNode = null;
 this.numberOfNodes = 0;
 }
 @Override
 public void clear() {
 this.rootNode = null;
 this.numberOfNodes = 0;
 }
 @Override
 public void insert(Key key, E element) {
 this.rootNode = this.insertHelp(this.rootNode, key, element);
 this.numberOfNodes++;
 }
 @Override
 public E remove(Key key) {
 // first find the node to remove
 E nodeToRemove = this.findHelp(this.rootNode, key);
 if (nodeToRemove != null) {
 // now remove the found node
 this.rootNode = this.removeHelp(this.rootNode, key);
 this.numberOfNodes--;
 }
 return nodeToRemove;
 }
 @Override
 public E removeRandomElement() {
 if (this.rootNode == null) {
 return null;
 }
 E randomeNodeToRemove = this.rootNode.getValue();
 this.rootNode = this.removeHelp(this.rootNode, this.rootNode.getKey());
 this.numberOfNodes--;
 return randomeNodeToRemove;
 }
 @Override
 public E find(Key key) {
 return this.findHelp(this.rootNode, key);
 }
 @Override
 public int size() {
 return this.numberOfNodes;
 }
 private E findHelp(BinarySearchTreeNode<Key, E> rootNode, Key key) {
 if (rootNode == null) {
 return null;
 }
 if (rootNode.getKey().compareTo(key) > 0) {
 return this.findHelp(rootNode.getLeftChild(), key);
 } else if (rootNode.getKey().compareTo(key) == 0) {
 return rootNode.getValue();
 } else {
 return this.findHelp(rootNode.getRightChild(), key);
 }
 }
 private BinarySearchTreeNode<Key, E> insertHelp(
 BinarySearchTreeNode<Key, E> rootNode, Key key, E element) {
 if (rootNode == null) {
 return new BinarySearchTreeNode<Key, E>(key, element, null, null);
 }
 if (rootNode.getKey().compareTo(key) > 0) {
 rootNode.setLeftChild(this.insertHelp(rootNode.getLeftChild(), key,
 element));
 } else {
 rootNode.setRightChild(this.insertHelp(rootNode.getRightChild(),
 key, element));
 }
 return rootNode;
 }
 private BinarySearchTreeNode<Key, E> removeHelp(
 BinarySearchTreeNode<Key, E> rootNode, Key key) {
 if (rootNode == null) {
 return null;
 }
 if (rootNode.getKey().compareTo(key) > 0) {
 rootNode.setLeftChild(this.removeHelp(rootNode.getLeftChild(), key));
 } else if (rootNode.getKey().compareTo(key) < 0) {
 rootNode.setRightChild(this.removeHelp(rootNode.getRightChild(),
 key));
 } else { // found node to remove
 if (rootNode.getLeftChild() == null) {
 return rootNode.getRightChild();
 } else if (rootNode.getRightChild() == null) {
 return rootNode.getLeftChild();
 } else { // there are 2 children
 BinarySearchTreeNode<Key, E> nodeToRemove = this
 .getNodeWithMinimumValue(rootNode.getRightChild());
 rootNode.setValue(nodeToRemove.getValue());
 rootNode.setKey(nodeToRemove.getKey());
 rootNode.setRightChild(this.deleteNodeWithMinimumValue(rootNode.getRightChild()));
 }
 }
 return rootNode;
 }
 private BinarySearchTreeNode<Key, E> getNodeWithMinimumValue(
 BinarySearchTreeNode<Key, E> rootNode) {
 if (rootNode.getLeftChild() == null) {
 return rootNode;
 }
 return this.getNodeWithMinimumValue(rootNode.getLeftChild());
 }
 private BinarySearchTreeNode<Key, E> deleteNodeWithMinimumValue(
 BinarySearchTreeNode<Key, E> rootNode) {
 if (rootNode.getLeftChild() == null) {
 return rootNode.getRightChild();
 }
 rootNode.setLeftChild(this.deleteNodeWithMinimumValue(rootNode.getLeftChild()));
 return rootNode;
 }
 // TODO: add traversal functions
}

Answer 1

When you have a custom implementation of something, and it has internal structures, like, in your case, the BinarySearchTreeNode, there is no real reason to have the interface for it. There is no public use of the interface, and not even your actual tree uses it. It is redundant. You can delete it, and remove the reference from the BinarySearchTreeNode

Additionally, there is no need for the BinarySearchTreeNode to be public. You never return the instance from the Tree, so there is no reason to expose it. Leaving it package-private (no public or private declaration) would be a decent choice, but commonly, the class is actually nested as a private-static inner class in the actual tree.

I am not sure what the Dictionary<> interface is ... Oh... really? java.util.Dictionary ... this should be java.util.Map<...> since the documentation for Dictionary (which, in 10 years, I have never seen before now) says:

NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.

Apart from that, the class looks pretty good.

public class BinarySearchTree<Key extends Comparable<? super Key>, E>
implements Map<Key, E> {
 private static class BinarySearchTreeNode<Key, E> {
 ....
 }
 .....
}

Answer 2

Just a small improvement: although this might be seen as a matter of taste, I personally find this kind of construction too verbose:

 if (this.leftChild == null && this.rightChild == null) {
 return true;
 } else {
 return false;
 }

You could easily convert it into a one-liner:

return (this.leftChild == null && this.rightChild == null);