public class BST<K extends Comparable<K>,V> implements Map<K,V>{

    private class Node{
        Node left;
        Node right;
        K key;
        V value;

        public Node(K k, V v){
            key=k;
            value=v;
            left=right=null;
         }

    }

    private Node root;
    private int numElem;

    public BST(){
        root=null;
        numElem = 0;
    }

    public int size(){
        return numElem;
    }

    public V get(K key){
        return get(root,key);
    }

    private V get(Node n ,K key){
        if(n == null) return null;

        if(n.key.compareTo(key) == 0 )
            return n.value;
        else if(n.key.compareTo(key) > 0 )
            return get(n.left,key);
        else
            return get(n.right,key);
    }

    public void set(K key, V value){
        root = set(root, key, value);
    }

    private Node set(Node n, K key, V value){
        if(n == null){
            //new node, increase the size
            numElem+=1;
            return new Node(key,value);
        }

        if(n.key.compareTo(key) == 0 ){

            //should we subtract or add to the size for a key that
            //previously existed?
            if(n.value != null && value == null)
                numElem-=1;

            if(n.value == null && value != null)
                numElem+=1;

            n.value=value;
            return n;
        } else if(n.key.compareTo(key) > 0 ){
            n.left = set(n.left,key,value);

        }else{
            n.right = set(n.right,key,value);
        }

        return n;
    }

    public List<K> keys(){
        ArrayList<K> list = new ArrayList<K>();
        keys(root,list);
        return list;
    }


    private void keys(Node n, ArrayList<K> l){
        if( n== null) return;
        keys(n.left, l);
        if(n.value != null) //shouldn't include keys with null values!
            l.push(n.key);
        keys(n.right, l);
    }

    public List<V> values(){
        ArrayList<V> list = new ArrayList<V>();
        values(root,list);
        return list;
    }


    private void values(Node n, ArrayList<V> l){
        if( n== null) return;
        values(n.left,l);
        if(n.value != null) //shouldn't include values that are null!
            l.push(n.value);
        values(n.right,l);
    }