/* El ancestro común más cercano en un árbol en O(1) de memoria Descripción Dado un árbol binario (que no es de búsqueda): struct Node { Node* parent; Node* left; Node* right; } Se necesita escribir una función que, para dos vértices dados, devuelva su ancestro común más cercano: Node* Lca (Node* a, Node* b); */

Para buscar el ancestro común más cercano (LCA) en un árbol binario con punteros a los padres y sin memoria adicional, se puede usar el siguiente enfoque:

1. Calcular la profundidad de cada uno de los dos vértices.
2. Elevar el vértice más profundo hacia arriba en la cadena de padres hasta que las profundidades sean iguales.
3. Luego, subir simultáneamente por los padres de ambos vértices hasta que coincidan, lo cual será el LCA.

Ejemplo en 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)

    // Elevar el nodo más profundo
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Subir juntos hasta encontrar el ancestro común
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Este algoritmo solo usa punteros y memoria constante, funciona en tiempo O(h), donde h es la altura del árbol.