/* Il più vicino antenato comune in un albero in O(1) di memoria Descrizione Dato un albero binario (non di ricerca): struct Node { Node* parent; Node* left; Node* right; } Deve essere scritta una funzione che, per due vertici dati, restituisce il loro antenato comune più vicino: Node* Lca (Node* a, Node* b); */

Per trovare il più vicino antenato comune (LCA) in un albero binario con puntatori ai genitori e senza memoria aggiuntiva, puoi usare il seguente approccio:

1. Calcola la profondità di ciascuno dei due vertici.
2. Solleva il vertice più profondo lungo la catena dei genitori finché le profondità non sono uguali.
3. Quindi, sali contemporaneamente lungo i genitori di entrambi i vertici finché non coincidono — questo sarà l'LCA.

Esempio in 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)

    // Solleva il nodo più profondo
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Salire insieme finché non si trova l'antenato comune
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Questo algoritmo utilizza solo puntatori e memoria costante, funziona in tempo O(h), dove h è l'altezza dell'albero.