Cominciamo dal calcolo del numero di foglie.
Penso che il problema si possa definire così:
Hai un albero binario, le foglie sono quei nodi che non hanno nè figlio destro nè figlio sinistro.
Quindi puoi immaginare una funzione che scorra l'albero e che incrementi una variabile GLOBALE quando incontra un nodo senza figli, quindi una foglia. In pseudo linguaggio dovrebbe essere così:

codice:
conta_foglie(T)
if (T!=NIL) //controllo che non sia un albero vuoto
  if (T.dx!=NIL) //se esiste un figlio destro allora visita il figlio destro
    conta_foglie(T.dx);
  if (T.sx!=NIL) //se esiste un figlio sinistro allora visita il figlio sinistro
    conta_foglie(T.sx);
  if (T.sx==NIL)AND(T.dx==NIL) //se non ha figli, allora incrementa la variabile GLOBALE FOGLIE
    foglie=foglie+1

Per quanto riguarda il livello massimo di profondità, è un pochettino più complicato...penso possa risolversi in questo modo. Porti dietro una variabile locale che si incrementa ogni volta che scendi di livello, confronti questo valora con un valore GLOBALE e ti salvi quello massimo.

codice:
conta_livello(T,liv)
if (T!=NIL) //controlla che non sia un albero vuoto
  if (T.dx!=NIL) //se ha un figlio destro, va a destra e incrementa il livello
    conta_livello(T.dx,liv+1)
  if (T.sx!=NIL) //se ha un figlio sinistro, va a sinistra e incrementa il livello
    conta_livello(T.sx,liv+1)
  if (T.sx==NIL)AND(T.dx==NIL) //se non ha figli, ha raggiunto una foglia
    if max<liv //confronta il valore del livello con una variabile GLOBALE e se è il massimo livello
      max=liv  //aggiorna la variabile GLOBALE
Spero siano funzioni corrette e che funzionino