/* Дарсдаги энг кичик умумий ата-она ўрнида 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 баландии дарахт аст.