/* Cel mai mic strămoș comun în arbore în O(1) memorie Descriere Se dă un arbore binar (nu de căutare): struct Node { Node* parent; Node* left; Node* right; } Trebuie să scrieți o funcție care, pentru două vârfuri date, să returneze cel mai mic (cel mai apropiat) strămoș comun: Node* Lca (Node* a, Node* b); */

Pentru a găsi cel mai apropiat strămoș comun (LCA) într-un arbore binar cu pointeri către părinți și fără memorie suplimentară, puteți folosi următoarea abordare:

1. Calculați adâncimea fiecăruia dintre cele două vârfuri.
2. Ridicați vârful mai adânc în sus pe lanțul părinților până când adâncimile sunt egale.
3. Apoi, urcați simultan pe lanțurile părinților ambelor vârfuri până când se întâlnesc — acesta va fi LCA.

Exemplu în 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)

    // Ridică nodul mai adânc
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Urcați împreună până găsiți strămoșul comun
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Acest algoritm folosește doar pointeri și memorie constantă, funcționează în timp O(h), unde h este înălțimea arborelui.