BinaryTree.java

public abstract class BinaryTree {
	
	private TreeNode root;
	
	public BinaryTree() {
		root = null;
	}
	
	public TreeNode getRoot() {
		return root;
	}
	
	protected void setRoot(TreeNode r) {
		root = r;
	}
	
	public boolean isEmpty() {
		return root == null;
	}
	
	public abstract void insert(Comparable obj);
	
	public abstract Comparable find(Comparable key);
	
	public void inOrder() {
		inOrder(root);
	}
	
	public void inOrder(TreeNode t) {
		if(t != null) {
			inOrder(t.getLeft());
			System.out.println(t.getValue() + " ");
			inOrder(t.getRight());
		}
	}
	
	class TreeNode {
		
		private Comparable value;
		private TreeNode left;
		private TreeNode right;
		
		public TreeNode(Comparable v, TreeNode l, TreeNode r) {
			value = v;
			left = l;
			right = r;
		}

		public Comparable getValue() {
			return value;
		}

		public void setValue(Comparable value) {
			this.value = value;
		}
		
		public boolean hasLeft() {
			return getLeft() == null;
		}
		
		public boolean hasRight() {
			return getRight() == null;
		}

		public TreeNode getLeft() {
			return left;
		}

		public void setLeft(TreeNode left) {
			this.left = left;
		}

		public TreeNode getRight() {
			return right;
		}

		public void setRight(TreeNode right) {
			this.right = right;
		}
		
		public boolean isLeaf() {
			return !hasRight() && !hasLeft();
		}
		
		public boolean hasExactlyOneChild() {
			return (hasRight() && !hasLeft()) || (hasLeft() && !hasRight());
		}
		
		public TreeNode getOnlyChild() {
			if(!hasExactlyOneChild())
				throw new UnsupportedOperationException("must have one child");
			if(hasRight())
				return getRight();
			else
				return getLeft();
		}
		
	}
	
}

BST.java

@SuppressWarnings("unchecked")
public class BST extends BinaryTree {
	
	@Override
	public Comparable find(Comparable key) {
		return findNode(key).getValue();
	}
	
	private TreeNode findNode(Comparable key) {
		if(key == null)
			throw new IllegalArgumentException();
		TreeNode p = null;
		TreeNode c = getRoot();
		while(c != null && key.compareTo(c.getValue()) != 0) {
			p = c;
			if(key.compareTo(c.getValue()) < 0) {
				c = c.getLeft();
			} else if(key.compareTo(c.getValue()) > 0) {
				c = c.getRight();
			}
		}
		return c; // ?
	}

	@Override
	public void insert(Comparable obj) {
		if(isEmpty())
			setRoot(new TreeNode(obj,null,null));
		else {
			TreeNode c = getRoot();
			TreeNode p = null;
			while(c != null) {
				p = c;
				if(obj.compareTo(c.getValue()) < 0)
					c = c.getLeft();
				else if(obj.compareTo(c.getValue()) > 0)
					c = c.getRight();
			}
			if(obj.compareTo(p.getValue()) < 0)
				p.setLeft(new TreeNode(obj,null,null));
			else if(obj.compareTo(p.getValue()) > 0)
				p.setRight(new TreeNode(obj,null,null));
		}
	}
	
	public void remove(Comparable key) {
		TreeNode p = null;
		TreeNode c = getRoot();
		while(c != null && key.compareTo(c.getValue()) != 0) {
			p = c;
			if(key.compareTo(c.getValue()) < 0) {
				c = c.getLeft();
			} else if(key.compareTo(c.getValue()) > 0) {
				c = c.getRight();
			}
		}
		if(p == null)
			return;
		if(c.isLeaf()) {
			if(c.getValue().compareTo(p.getValue()) > 0)
				p.setRight(null);
			else
				p.setLeft(null);
		} else if(c.hasExactlyOneChild()) {
			if(c.getValue().compareTo(p.getValue()) > 0) {
				p.setRight(c.getOnlyChild());
			} else {
				p.setLeft(c.getOnlyChild());				
			}
		} else {
			// find largest node in left subtree
			// and that node's parent
			
		}
	}
	
	public TreeNode max() {
		return max(getRoot());
	}
	
	public TreeNode max(TreeNode t) {
		TreeNode c = t;
		TreeNode p = null;
		while(c != null) {
			p = c;
			c = c.getRight();
		}
		return p;
	}
	
}