Vérifier qu'un arbre est un ABR

Il ne suffit pas de comparer chaque nœud à ses enfants directs : il faut que toutes les valeurs d'un sous-arbre respectent un intervalle autorisé. On transmet donc une borne minimale et une borne maximale, resserrées à chaque descente.

def est_abr(arbre, mini=float('-inf'), maxi=float('inf')):
    if arbre is None:
        return True
    if not (mini < arbre.valeur < maxi):
        return False
    return (est_abr(arbre.gauche, mini, arbre.valeur)
            and est_abr(arbre.droit, arbre.valeur, maxi))

En descendant à gauche, la valeur du nœud devient la nouvelle borne maximale ; en descendant à droite, elle devient la nouvelle borne minimale. Coût $O(n)$.