/* Menor ancestral comum na árvore em O(1) memória Descrição Dada uma árvore binária (não de busca): struct Node { Node* parent; Node* left; Node* right; } É necessário escrever uma função que, para dois vértices dados, retorne seu menor (mais próximo) ancestral comum: Node* Lca (Node* a, Node* b); */

Para procurar o ancestral comum mais próximo (LCA) numa árvore binária com ponteiros para os pais e sem memória adicional, pode usar a seguinte abordagem:

1. Calcular a profundidade de cada um dos dois vértices.
2. Levantar o vértice mais profundo na cadeia de pais até que as profundidades fiquem iguais.
3. Depois, subir simultaneamente pelos pais de ambos os vértices até que coincidam — esse será o LCA.

Exemplo em 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)

    // Levantar o nó mais profundo
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Subir juntos até encontrar o ancestral comum
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Este algoritmo usa apenas ponteiros e memória constante, funciona em tempo O(h), onde h é a altura da árvore.