/* Der nächste gemeinsame Vorfahre in einem Baum in O(1) Speicher Beschreibung Gegeben ist ein binärer Baum (kein Suchbaum): struct Node { Node* parent; Node* left; Node* right; } Es ist eine Funktion zu schreiben, die für zwei gegebene Knoten ihren nächsten gemeinsamen Vorfahren zurückgibt: Node* Lca (Node* a, Node* b); */

Um den nächstgelegenen gemeinsamen Vorfahren (LCA) in einem binären Baum mit Zeigern auf die Eltern und ohne zusätzlichen Speicher zu finden, kann man den folgenden Ansatz verwenden:

1. Berechne die Tiefe jeder der beiden Knoten.
2. Hebe den tieferen Knoten nach oben in der Elternkette, bis die Tiefen gleich sind.
3. Gehe dann gleichzeitig nach oben in der Elternkette beider Knoten, bis sie übereinstimmen — das ist der LCA.

Beispiel in 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)

    // Hebe den tieferen Knoten nach oben
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Gehe gemeinsam nach oben, bis sie übereinstimmen
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Dieser Algorithmus verwendet nur Zeiger und konstanten Speicher, läuft in O(h) Zeit, wobei h die Höhe des Baumes ist.