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.