Problème — Plus proche ancêtre commun dans un ABR

La propriété d'ordre simplifie beaucoup le problème. Si a et b sont tous deux inférieurs au nœud courant, leur ancêtre commun est dans le sous-arbre gauche ; s'ils sont tous deux supérieurs, il est à droite. Sinon (les deux valeurs encadrent le nœud courant, ou l'une vaut le nœud), le nœud courant est lui-même l'ancêtre commun cherché.

def ancetre_commun(arbre, a, b):
    noeud = arbre
    while noeud is not None:
        if a < noeud.valeur and b < noeud.valeur:
            noeud = noeud.gauche
        elif a > noeud.valeur and b > noeud.valeur:
            noeud = noeud.droit
        else:
            return noeud.valeur       # point de separation
    return None

On suit un unique chemin depuis la racine jusqu'au « point de séparation » où les deux valeurs divergent : le coût est $O(h)$, soit $O(\log n)$ pour un arbre équilibré. Par exemple, dans l'ABR de l'exemple, l'ancêtre commun de 4 et 7 est 6, et celui de 1 et 13 est la racine 8.