Ce n'est pas très dur.

let rec compte_feuilles a = match a with | Feuille _ -> 1 | Noeud (c1,c2,c3,c4) -> (* noms de variables selon l'énoncé *) compte_feuilles c1 + compte_feuilles c2 + compte_feuilles c3 + compte_feuilles c4 ;;

Ce style de programmation par filtrage sur les deux sortes d'arbre possibles se retrouvera par la suite.

Notez l'emploi de « underscore » dans le motif Feuille _. Il est de bon ton, puisque l'argument du constructeur Feuille n'est pas pertinent, de le signaler franchement ainsi.