BST.java

public class BST<T extends Comparable<? super T>> {


	private Node root;
	private int size = 0;

	public void insert(T value) {
		root = insert(value,root);
	}
	/**
	 * Keep in mind that this does not produce
	 * a balanced tree
	 */
	private Node insert(T value, Node node) {
		if(node == null){
			size++;
			node = new Node(value);
		} 
		int cmp = value.compareTo(node.getValue());
		if(cmp < 0) {
			node.leftChild = insert(value,node.leftChild);
		}else if(cmp > 0) {
			node.rightChild = insert(value,node.rightChild);
		}
		return node;
	}

	public boolean contains(T value) {
		return contains(value,root);
	}
	private boolean contains(T value, Node node) {
		if(node==null)
			return false;
		int cmp = value.compareTo(node.getValue());
		if(cmp < 0) {
			return contains(value,node.leftChild);
		} else if(cmp == 0){
			return true;
		} else  {
			return contains(value,node.rightChild); 
		}
	}

	public int size() {
		return size;
	}

	public int depth() {
		return depth(0,root);
	}
	private int depth(int d,Node node) {
		if(node==null)
			return d;
		return Math.max(depth(d+1,node.leftChild),depth(d+1,node.rightChild));
	}

	private class Node {
		public Node leftChild, rightChild;
		private T value;

		public Node(T val) {
			value = val;
		}
		public T getValue() {
			return value;
		}
	}

	public static void main(String[] args) {
		BST<String> tree = new BST<String>();
		String[] toInsert = {"aunt","uncle","son","daughter","aunt"};
		for (String string : toInsert) {
			tree.insert(string);
		}
		String[] toFind = {"aunt","uncle","son","daughter","dog"};
		for (String string : toFind) {
			System.out.println("Contains "+string+": "+tree.contains(string));
		}
		System.out.println("Tree depth="+tree.depth());
	}

}