/* Mazākais kopīgais senelis kokā ar O(1) atmiņu Apraksts Dota binārais koks (ne meklēšanas): struct Node { Node* parent; Node* left; Node* right; } Ir jāuzraksta funkcija, kas diviem dotajiem mezgliem atgriež viņu mazāko (tuvāko) kopīgo seneli: Node* Lca (Node* a, Node* b); */

Lai atrastu tuvāko kopīgo senču (LCA) binārajā kokā ar vecāku norādītājiem un bez papildu atmiņas, var izmantot sekojošo pieeju:

1. Aprēķiniet katra no diviem mezgliem dziļumu.
2. Paceliet dziļāko mezglu augšup pa vecāku ķēdi, līdz dziļumi sakrīt.
3. Tad vienlaikus kāpiet augšup pa abu mezglu vecāku ķēdēm, līdz tie saskaras — tas būs LCA.

Piemērs Go valodā:

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)

    // Pacel dziļāko mezglu
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Kāpiet kopā, līdz saskarsieties
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Šis algoritms izmanto tikai norādes un konstantu atmiņu, tas darbojas laikā O(h), kur h ir koka augstums.