/* Väikseim ühine esivanem puus O(1) mälu kasutades Kirjeldus Antud on binaarne puu (mitte otsingupuu): struct Node { Node* parent; Node* left; Node* right; } On vaja kirjutada funktsioon, mis kahe antud tipu jaoks tagastab nende väikseima (lähemalse) ühise esivanema: Node* Lca (Node* a, Node* b); */

Kokkuvõtteks lähima ühise esivanema (LCA) leidmiseks binomilises puus, kus on vanemate näidikud ja ilma täiendava mäluta, saab kasutada järgmist lähenemist:

1. Arvuta iga kahe tipu sügavus.
2. Tõsta sügavam tipp ülespoole vanemate ahelas, kuni sügavused on võrdsed.
3. Seejärel tõusege mõlema tipu vanemate ahelas koos üles, kuni nad kohtuvad — see on LCA.

Näide Go keeles:

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)

    // Tõsta sügavam tipp ülespoole
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Koos ülespoole, kuni leitakse ühine esivanem
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

See algoritm kasutab ainult näidikuid ja konstantsel mälul, töötab O(h) ajal, kus h on puu kõrgus.