/* Najmenší spoločný predok v strome v O(1) pamäti Popis Dá sa binárny strom (nie vyhľadávací): struct Node { Node* parent; Node* left; Node* right; } Je potrebné napísať funkciu, ktorá pre dve dané vrcholy vráti ich najmenšie (najbližšie) spoločné predka: Node* Lca (Node* a, Node* b); */

Na nájdenie najbližšieho spoločného predka (LCA) v binárnom strome s ukazovateľmi na rodičov a bez dodatočnej pamäte môžete použiť nasledujúci prístup:

1. Spočítajte hĺbku každého z dvoch vrcholov.
2. Vyššiu vrstvu zdvihnite hore po reťazci rodičov, kým sa hlbky nevyrovnajú.
3. Potom, súčasne stúpajte hore po reťazcoch rodičov oboch vrcholov, kým sa nestretnú — to bude LCA.

Príklad v 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)

    // Zdvíhajte hlbší vrchol
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Spoločne stúpajte hore, kým nenájdete spoločného predka
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Tento algoritmus používa iba ukazovatele a konštantnú pamäť, pracuje v čase O(h), kde h je výška stromu.