/* Ağaçta O(1) hafıza ile en küçük ortak ata Açıklama İkili ağaç verildi (arama ağacı değil): struct Node { Node* parent; Node* left; Node* right; } İki düğüm verildiğinde, bunların en küçük (en yakın) ortak atasını döndüren bir fonksiyon yazmanız gerekiyor: Node* Lca (Node* a, Node* b); */

İki düğümün en yakın ortak atasını (LCA) ebeveynlere işaretçileri olan ve ek hafıza kullanmayan ikili ağaçta bulmak için aşağıdaki yaklaşımı kullanabilirsiniz:

1. Her iki düğümün derinliğini hesaplayın.
2. En derin düğümü, derinlikler eşit olana kadar ebeveyn zincirinde yukarı kaldırın.
3. Ardından, her iki düğümün ebeveynleriyle birlikte yukarı çıkmaya devam edin, ta ki eşleşene kadar — bu LCA olacaktır.

Go dilinde örnek:

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)

    // En derin düğümü yukarı kaldır
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Birlikte yukarı çıkın, ortak atasını bulun
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Bu algoritma sadece işaretçiler ve sabit hafıza kullanır, O(h) sürede çalışır, burada h ağacın yüksekliğidir.