Compter les feuilles

Une feuille est un nœud dont les deux sous-arbres sont None. On distingue trois cas : l'arbre vide, la feuille, et le nœud interne.

def nb_feuilles(arbre):
    if arbre is None:
        return 0
    if arbre.gauche is None and arbre.droit is None:
        return 1                      # c'est une feuille
    return nb_feuilles(arbre.gauche) + nb_feuilles(arbre.droit)

Chaque nœud est visité une fois, le coût est $O(n)$.