/* Le plus proche ancêtre commun dans un arbre en O(1) de mémoire Description Donné un arbre binaire (pas un arbre de recherche) : struct Node { Node* parent; Node* left; Node* right; } Il faut écrire une fonction qui, pour deux sommets donnés, retourne leur plus proche ancêtre commun : Node* Lca (Node* a, Node* b); */

Pour rechercher l'ancêtre commun le plus proche (LCA) dans un arbre binaire avec des pointeurs vers les parents et sans mémoire supplémentaire, vous pouvez utiliser l'approche suivante :

1. Calculer la profondeur de chacun des deux sommets.
2. Élever le sommet le plus profond vers le haut dans la chaîne des parents jusqu'à ce que les profondeurs soient égales.
3. Ensuite, monter simultanément dans la chaîne des parents des deux sommets jusqu'à ce qu'ils se rencontrent — c'est le LCA.

Exemple en Go :

type Node struct {
    parent *Node
    left   *Node
    right  *Node
}

func depth(n *Node) int {
    d := 0
    for n != nil {
        n = n.parent
        d++
    }
    return d
}

func Lca(a, b *Node) *Node {
    da := depth(a)
    db := depth(b)

    // Élever le nœud le plus profond
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Monter ensemble jusqu'à trouver l'ancêtre commun
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Cet algorithme n'utilise que des pointeurs et de la mémoire constante, fonctionne en temps O(h), où h est la hauteur de l'arbre.