Valeur maximale d'un arbre binaire

On compare la valeur de la racine aux maximums des deux sous-arbres. Pour gérer les sous-arbres vides, on leur attribue une valeur « neutre » très petite.

def maximum(arbre):
    m = arbre.valeur
    if arbre.gauche is not None:
        m = max(m, maximum(arbre.gauche))
    if arbre.droit is not None:
        m = max(m, maximum(arbre.droit))
    return m

Comme on parcourt tous les nœuds, le coût est $O(n)$. Remarque : dans un ABR, le maximum est plus simple à trouver, c'est le nœud le plus à droite, idée symétrique de celle employée pour supprimer une valeur dans un ABR.