/* Oʻzaro boʻlgan daraxtda eng kichik umumiy ajdodni O(1) xotira bilan topish Tavsif Binar daraxt berilgan (qidiruv emas): struct Node { Node* parent; Node* left; Node* right; } Ikki berilgan tugun uchun ularning eng kichik (yaqin) umumiy ajdodini qaytaradigan funktsiya yozish kerak: Node* Lca (Node* a, Node* b); */

Ikki bog'ning eng yaqin umumiy ajdodini (LCA) ota-onalarga ishora qiluvchi ko'rsatkichlar bilan va qo'shimcha xotira olmadan topish uchun quyidagi yondashuvni qo'llash mumkin:

1. Ikkala nuqtaning har birining chuqurligini hisoblang.
2. Eng chuqur nuqtani ota-onalar zanjirida yuqoriga ko'taring, chuqurliklar tenglashguncha.
3. So'ngra, ikkala nuqtaning ota-onalariga birgalikda yuqoriga chiqib, ular mos kelguncha — bu LCA bo'ladi.

Go tilida misol:

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)

    // Eng chuqur tugunni ko'taring
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Birgalikda yuqoriga chiqib, umumiy ajdodni toping
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Ushbu algoritm faqat ko'rsatkichlar va doimiy xotira ishlatadi, O(h) vaqt ichida ishlaydi, bu yerda h daraxtning balandligi.