Binary Search Tree

Hola buenas noches,soy nuevo en el foro y me han pedido un trabajo de árbol binario y no se como empezarlo o hacerlo. Si me pudieseis decir como se hace os lo agradecería.
Me han dado una clase Diccionario, una clase BST y una clase Nodo.
La clase Diccionario es la siguiente:

Código:

public interface Diccionario {
	
	/**
     * Mete un valor nuevo.
     * Si ya existe uno con misma clave, reemplaza el valor.
     *
     * @param clave
     * @param valor
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     * @throws RuntimeException Si no cabe la clave.
     */
    void put(String clave, String valor);
    	   
    

    /**
     * Saca el valor asociado a la clave.
     *
     * @param clave
     * @return null si no estÃ¡ la clave.
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     */
    String get(String clave);

    /**
     * Elimina el objeto asociado a la clave, si estÃ¡.
     *
     * @param clave
     * @return devuelve el valor asociado si estaba la clave; devuelve null si no estÃ¡ la clave
     * @throws IllegalArgumentException Si clave es null.
     * @throws IllegalArgumentException Si clave es la cadena vacia.
     */
    String remove(String clave);

    /**
     * @return nÃºmero de elementos almacenados.
     */
    int size();

    /**
     * Elimina todas las claves.
     */
    void clear();
}

Esta clase no hace falta hacer nada con ella solo sirve para que la clase BST la implemente.

La clase BST es la siguiente:

Código:

public class BST implements Diccionario {
	
	private Nodo root;
	private int nDatos;
	
    public BST(){
    	root = null;
    	nDatos = 0;
	}

Esta es la clase que hay que hacer

Y finalmente la clase nodo que tampoco hay que completarla:

Código:

public class Nodo {
	String clave;
	String valor;
	Nodo izq;
	Nodo der;
	
	public Nodo (String clave,String valor){
		this.clave = clave;
		this.valor = valor;
	}

}

Si me pudierais ayudar con la realización de la misma os lo agradecería mucho.
Gracias de antemano.