/* A legkisebb közös ős a fában O(1) memóriával Leírás Adott egy bináris fa (nem keresőfa): struct Node { Node* parent; Node* left; Node* right; } Írjon egy függvényt, amely két adott csúcs esetén visszaadja azok legkisebb (legközelebbi) közös ősét: Node* Lca (Node* a, Node* b); */

Közeli közös ős (LCA) megtalálásához egy bináris fában, amelyben a szülőkre mutató mutatók vannak, és nincs további memória, a következő megközelítést alkalmazhatja:

1. Számolja ki mindkét csúcs mélységét.
2. Emelje fel a mélyebb csúcsot a szülők láncán, amíg a mélységek nem egyeznek.
3. Ezután egyidejűleg haladjon felfelé mindkét csúcs szülőin, amíg össze nem érnek — ez lesz az LCA.

Példa Go nyelven:

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)

    // Emelje fel a mélyebb csúcsot
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Együtt haladjon felfelé, amíg meg nem találja a közös ősét
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Ez az algoritmus csak mutatókat és konstans memóriát használ, O(h) idő alatt működik, ahol h a fa magassága.