/* Дарахтта эң кичүү жалпы ата-эне O(1) эс тутумда Тасвир Бинар дарак берилген (издөө эмес): struct Node { Node* parent; Node* left; Node* right; } Эки берилген түйүн үчүн алардын эң кичүү (жакынкы) жалпы ата-энесин кайтарган функция жазуу керек: Node* Lca (Node* a, Node* b); */

Ике чекиттин эң жакын жалпы ата-эне (LCA) табуу үчүн, ата-эне көрсөткүчтөрү бар жана кошумча эс тутуму жок, төмөнкү ыкманы колдонсо болот:

1. Эки чекиттин ар биринин тереңдигин эсептеңиз.
2. Аягында эң терең чекитти ата-эне чынжыры боюнча көтөрүңүз, тереңдиктер теңескенге чейин.
3. Андан кийин, эки чекиттин ата-эне чынжырлары боюнча бирдей көтөрүлүп, алар кездешкенче — бул LCA болот.

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)

    // Эң терең чекитти көтөрүңүз
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Бирге көтөрүлүп, жалпы ата-энени табыңыз
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Бул алгоритм гана көрсөткүчтөрдү жана туруктуу эс тутумду колдонуп, убакытта O(h) иштейт, анда h — дарактын бийиктиги.