/* Nejmenší společný předek v stromu s pamětí O(1) Popis Dán binární strom (ne vyhledávací): struct Node { Node* parent; Node* left; Node* right; } Je třeba napsat funkci, která pro dvě zadané vrcholy vrátí jejich nejmenší (nejbližší) společný předek: Node* Lca (Node* a, Node* b); */

Pro nalezení nejbližšího společného předka (LCA) v binárním stromu s ukazateli na rodiče a bez dodatečné paměti lze použít následující přístup:

1. Spočítejte hloubku každého z obou vrcholů.
2. Vyšší vrchol vytáhněte vzhůru po řetězci rodičů, dokud se hloubky nevyrovnají.
3. Poté současně stoupejte vzhůru po řetězci rodičů obou vrcholů, dokud se nesetkají — to bude LCA.

Pří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)

    // Vyšší vrchol vytáhněte vzhůru
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Společně stoupejte vzhůru, dokud nenajdete společného předka
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Tento algoritmus používá pouze ukazatele a konstantní paměť, pracuje v čase O(h), kde h je výška stromu.