Binary tree'de iki düğümün en yakın ortak atasını (Lowest Common Ancestor) bulun.

Özyinelemeli çözüm: bir düğümden aşağı inip p veya q'yu arayın. Bir düğümün sol alt ağacından biri, sağ alt ağacından diğeri dönüyorsa o düğüm LCA'dır. Yalnızca bir taraftan sonuç geliyorsa o sonucu yukarı taşıyın.

def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root          # p ve q farklı taraflarda
    return left or right     # ikisi de aynı tarafta (veya hiç bulunamadı)

Bu çözüm, bir düğümün kendisinin atası sayılabildiğini kabul eder: p, q'nun atasıysa cevap p'dir.

Karmaşıklık

O(n) zaman, O(h) özyineleme yığını.

Binary Search Tree ise daha basit

BST'de değerleri karşılaştırarak tek bir yol boyunca ineriz:

def lca_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node      # ayrılma noktası

Bu O(h) zaman ve O(1) bellektir.

Varyasyonlar

• Düğümlerin parent işaretçisi varsa: iki bağlı listenin kesişimini bulma problemine dönüşür.
• p veya q ağaçta olmayabilirse: ikisinin de bulunduğunu ayrıca doğrulamak gerekir.