/* Mažiausias bendras protėvis medyje naudojant O(1) atmintį Aprašymas Duotas binarinis medis (ne paieškos): struct Node { Node* parent; Node* left; Node* right; } Reikia parašyti funkciją, kuri dviem duotiems mazgams grąžins jų mažiausią (artimiausią) bendrą protėvį: Node* Lca (Node* a, Node* b); */

Norint rasti artimiausią bendrą protėvį (LCA) dvejetainėje medyje su tėvų nuorodomis ir be papildomos atminties, galima naudoti šį požiūrį:

1. Apskaičiuokite kiekvieno iš dviejų viršūnių gylį.
2. Pakelkite giliau esantį viršūnę aukštyn tėvų grandine, kol gyliai taps lygūs.
3. Tada, vienu metu kylant aukštyn abiejų viršūnių tėvų grandinėmis, kol jos susitiks — tai bus LCA.

Pavyzdys Go kalba:

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)

    // Pakelkite giliau esantį viršūnę
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Kylant kartu aukštyn, kol susitiks — tai bus LCA
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Šis algoritmas naudoja tik nuorodas ir pastovią atmintį, veikia O(h) laiku, kur h yra medžio aukštis.