/* Najbliższy wspólny przodek w drzewie w czasie O(1) pamięci Opis Dane jest drzewo binarne (nie wyszukiwawcze): struct Node { Node* parent; Node* left; Node* right; } Należy napisać funkcję, która dla dwóch danych wierzchołków zwróci ich najbliższego wspólnego przodka: Node* Lca (Node* a, Node* b); */

Aby znaleźć najbliższego wspólnego przodka (LCA) w drzewie binarnym z wskaźnikami na rodziców i bez dodatkowej pamięci, można użyć następującego podejścia:

1. Oblicz głębokość każdego z dwóch wierzchołków.
2. Podnieś głębszy wierzchołek wzdłuż łańcucha rodziców, aż głębokości się wyrównają.
3. Następnie, jednocześnie wspinaj się wzdłuż łańcuchów rodziców obu wierzchołków, aż się spotkają — to będzie LCA.

Przykład w 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)

    // Podnieś głębszy wierzchołek
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Wspólnie wspinaj się, aż znajdziesz wspólnego przodka
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Ten algorytm używa tylko wskaźników i pamięci stałej, działa w czasie O(h), gdzie h to wysokość drzewa.