public class BinarySearchTree <K extends Comparable <? super K>, V>{
	private class Node {
		K key;
		V data;
		Node left, right;
		Node (K key, V data) {
			this.key = key;
			this.data = data;
		}
	}

	Node root = null;
	
	// Insert K and V into the subtree rooted at cur
	// returns the root of the new tree
	private Node insertHelper(K key, V data, Node cur) {
		if (cur == null) 
			return new Node (key, data);
		
		if(key.compareTo(cur.key)>0)
			cur.right = insertHelper(key, data, cur.right);
		else // breaks ties to the left and inserts a new node; how to handle duplicate keys depends -- for instance, maybe we should just replace the data and not create a new node
			cur.left = insertHelper (key, data, cur.left); 
		return cur;
	}
	
	public void insert (K key, V data) {
		insertHelper(key, data, root);
	}
	
	public V lookup (K key) {
		Node cur = root;
		while(cur!=null) {
			int result = key.compareTo(cur.key);
			if (result == 0)
  				return cur.data;
			else if (result < 0)
				cur = cur.left;
			else
				cur = cur.right;
		}
		return null;
	}
	public void delete (K key) {
		root = delete(key, root);
	}
	// deleted key from the tree rooted at cur, if key exists in that tree
	// returns the root of the new tree
	// modifies nothing if key doesn't exist in the tree rooted at cur
	private Node delete (K key, Node cur) {
		if (cur==null)
			return null;
		int result = key.compareTo(cur.key);
		if (result == 0) { // have to delete cur
			if (cur.left == null) // this covers only a right child or no children at all
				return cur.right;
			if (cur.right == null) // this covers only a left child
				return cur.left;
			
			Node inOrderSuccessor = cur.right, inOrderSuccessorParent = cur;
			while (inOrderSuccessor.left!=null) {
				inOrderSuccessorParent = inOrderSuccessor;
				inOrderSuccessor = inOrderSuccessor.left;
			}
			
			if (inOrderSuccessorParent == cur) // the while loop did nothing, because the successor is just the right child of cur
				// equivalently, we could check if inOrderSuccessorParent.right == inOrderSuccessor
				cur.right = inOrderSuccessor.right;
			else
				inOrderSuccessorParent.left = inOrderSuccessor.right;
			
			cur.key = inOrderSuccessor.key;
			cur.data = inOrderSuccessor.data;
			
			return cur;			
		}
		else { // the deletion happens in one of my subtrees
			if (result < 0)
				cur.left = delete(key, cur.left);
			else
				cur.right = delete(key, cur.right);
			return cur;
		}
		
	}
}