One solution to the generic BST problem.
Note that T can be any class whose objects are comparable to other objects of that class. Since objects must be comparable in this way, the only possible meaning for a node with a null datum must be that it is an empty tree.
public class BST<T extends Comparable<T>> { private T datum; private BST<T> left; private BST<T> right; public BST() { datum = null; // this is our notion of an empty tree } public BST(T datum) { this.datum = datum; left = null; right = null; } public BST(T datum, BST<T> left, BST<T> right) { this.datum = datum; this.left = left; this.right = right; } public boolean isEmpty() { return (datum == null); } public T getDatum() { return datum; } public BST<T> getLeft() { return left; } public BST<T> getRight() { return right; } public boolean isLeaf() { return (!(datum == null) && (getLeft() == null) && (getRight() == null)); } public void insert(T datum) { if (this.datum.compareTo(datum) > 0) { if (left != null) { left.insert(datum); } else { left = new BST<T>(datum); } } else if (this.datum.compareTo(datum) < 0) { if (right != null) { right.insert(datum); } else { right = new BST<T>(datum); } } } public int depth() { if (isEmpty()) return 0; else { return (int) (1 + (Math.max( left == null ? 0 : left.depth(), right == null ? 0 : right.depth()))); } } public boolean contains(T datum) { if (isEmpty()) return false; if (datum.compareTo(this.datum) < 0) { if (left == null) { return false; } else { return left.contains(datum); } } else if (datum.compareTo(this.datum) > 0) { if (right == null) { return false; } else { return right.contains(datum); } } else { return true; } } public void printInOrder() { if (isEmpty()) System.out.println("null"); else { if (left != null) left.printInOrder(); System.out.print(datum + " "); if (right != null) right.printInOrder(); } } public void printPreOrder() { if (isEmpty()) System.out.println("null"); else { System.out.print(datum + " "); if (left != null) left.printPreOrder(); if (right != null) right.printPreOrder(); } } public String toString() { if (isEmpty()) return "Empty tree"; else return "Tree with root " + datum; } }