/* Najbliži zajednički predak u stablu u O(1) memorije Opis Dat je binarno stablo (ne pretraživačko): struct Node { Node* parent; Node* left; Node* right; } Potrebno je napisati funkciju koja za dva data čvora vraća njihov najbliži zajednički predak: Node* Lca (Node* a, Node* b); */

Za pronalazak najbližeg zajedničkog pretka (LCA) u binarnom stablu sa pokazivačima na roditelje i bez dodatne memorije, možete koristiti sledeći pristup:

1. Izračunajte dubinu svakog od dva čvora.
2. Podignite dublji čvor uzlazno kroz lanac roditelja dok dubine ne budu jednake.
3. Zatim, istovremeno se penju uzlazno kroz lance roditelja oba čvora dok se ne susretnu — to će biti LCA.

Primer u 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)

    // Podignite dublji čvor
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Istovremeno se penju dok se ne susretnu
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Ovaj algoritam koristi samo pokazivače i konstantnu memoriju, radi u vremenu O(h), gde je h visina stabla.