/* Ağacda O(1) yaddaşla ən kiçik ümumi ata Təsviri Verilən ikili ağac (axtarış deyil): struct Node { Node* parent; Node* left; Node* right; } İki verilmiş düyün üçün onların ən kiçik (ən yaxın) ümumi atasını qaytaran funksiya yazmalısınız: Node* Lca (Node* a, Node* b); */

İki ulduzun ən yaxın ümumi atasını (LCA) ata göstəriciləri olan və əlavə yaddaş olmadan tapmaq üçün aşağıdakı yanaşmadan istifadə edə bilərsiniz:

1. Hər iki ulduzun dərinliyini hesablayın.
2. Daha dərin ulduzu ata göstəriciləri boyunca yuxarı qaldırın, dərinliklər bərabər olana qədər.
3. Sonra, hər iki ulduzun ata göstəriciləri boyunca birlikdə yuxarı qalxın, onlar uyğunlaşana qədər — bu, LCA olacaq.

Go dilində nümunə:

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)

    // Daha dərin ulduğu yuxarı qaldırın
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Birlikdə yuxarı qalxın, ümumi ata tapana qədər
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Bu alqoritm yalnız göstəricilər və sabit yaddaş istifadə edir, O(h) vaxtda işləyir, burada h ağacın hündürlüyüdür.