Ciao, una cosa che ho notato è che in:
IF(chiave(r) == k) THEN return k
Io invece di k che è il valore cercato, restituirei il (puntatore) all'elemento trovato,
oppure TRUE, dipende da come vuoi strutturare la tua funzione. Mi sembra più logico.

Poi a livello di ricorsione, io credo che nella maniera che hai programmato tu,
la prima funzione chiamante riceve un valore solamente se l'albero è vuoto
oppure il valore è nella radice. Mi spiego meglio..
(prendila con il beneficio del dubbio non sono mai stato un fenomeno nel ricorsivo):

Una funzione quando fa return, restituisce il valore alla funzione che l'ha chiamata..
adesso metti il caso che il valore cercato non sia nel primo elemento e quindi si va in:

CercaElemento(nodo figlio sinistro di r, chiave k)

Adesso, il valore è quello giusto, la funzione ritorna k, ma la funzione chiamante il k non lo riceve..

??? = CercaElemento(nodo figlio sinistro di r, chiave k).



Io non ho avuto modo di testarlo però ho pensato a questa soluzione:

codice:
CercaElemento(nodo r, chiave k) {
   IF (r == NULL) THEN return NULL
   IF (chiave(r) == k) THEN return r

   res = CercaElemento(figlio sx di r, k)
   IF (res != NULL) return res;
   res = CercaElemento(figlio dx di r, k)
   IF (res != NULL) return res;

   return NULL;
Forse ho scritto delle sciocchezze, se così fosse scusami