/* Най-малкият общ прародител в дървото с 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 е височината на дървото.