J'ai saisis l'idée, mais je ne comprend pas comment je peux obtenir les deux arguments de p (la hauteur du sous arbre gauche et la hauteur du sous arbre droit).
Je vais essayer d'expliciter la réponse de Marc Zeitoun.
Vous travaillez sur un arbre de type 'a btree.
Une suggestion possible est de calculer, pour chaque noeud de l'arbre, un couple (b,h) où b est un certain booléen (est-ce que le sous-arbre est équilibré) et h est la hauteur de cet arbre.
Cela correspond à calculer un nouvel arbre, de type
'a * bool * int btree
qui sera une "conversion" de votre arbre: à chaque noeud, vous aurez, en plus de l'étiquette du noeud correspondant de votre arbre de départ, le booléen demandé pour ce noeud, et l'entier demandé pour ce noeud.
Si vous vous y prenez correctement, le calcul de ce nouvel arbre se fera en temps O( n ) où n est la taille de l'arbre - temps linéaire, c'est-à-dire pas plus que ce que cela coûte de parcourir l'arbre (et de toute manière, votre fonction [b]doit[/b] parcourir l'arbre).
Et notez que, parce que la définition du type 'a btree est déjà polymorphe, vous n'avez pas besoin de définir de type supplémentaire pour ce faire! (un 'a * bool * int btree est un cas particulier du type déjà défini)
Ceci étant dit, il n'y a pas réellement besoin de calculer cet arbre "décoré". La seule chose qui vous intéresse dans cet arbre, au fond, c'est la décoration de la racine. Or, si vous y réfléchissez, vous allez voir que la décoration de chaque noeud dépend uniquement des décorations de ses fils. Résultat, vous pouvez vous en sortir en écrivant une fonction qui calcule ces deux informations pour un arbre: récursivement, pour calculer la décoration de la racine d'un arbre, on calcule la décoration des racines de ses deux sous-arbres (i.e. on appelle la fonction sur les deux sous-arbres), et en fonction des résultats, on peut calculer (en temps constant) le résultat de la fonction sur l'arbre. (Bien sûr, dans cette description, je ne parle pas de ce qui se passe sur les cas terminaux, souvent les arbres vides)
Ce genre de généralisation de la fonction qu'on cherche à écrire n'est pas rare (on veut calculer f(x), et il s'avère que c'est mieux de calculer conjointement le couple (f(x),g(x))). C'est déjà la "bonne" façon de décider si un arbre est quasi-parfait, par exemple.