/* Kleinste gemeenschappelijke voorouder in een boom in O(1) geheugen Beschrijving Gegeven een binaire boom (geen zoekboom): struct Node { Node* parent; Node* left; Node* right; } Je moet een functie schrijven die voor twee gegeven knooppunten hun kleinste (dichtstbijzijnde) gemeenschappelijke voorouder teruggeeft: Node* Lca (Node* a, Node* b); */

Om de dichtstbijzijnde gemeenschappelijke voorouder (LCA) te vinden in een binaire boom met pointers naar de ouders en zonder extra geheugen, kun je de volgende aanpak gebruiken:

1. Bereken de diepte van elk van de twee knooppunten.
2. Verhoog het dieper gelegen knooppunt omhoog langs de ouderketen totdat de diepten gelijk zijn.
3. Ga vervolgens gelijktijdig omhoog langs de ouderketens van beide knooppunten totdat ze samenkomen — dat is de LCA.

Voorbeeld 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)

    // Verhoog het dieper gelegen knooppunt
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Ga samen omhoog totdat je de gemeenschappelijke voorouder vindt
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Dit algoritme gebruikt alleen pointers en constante geheugenruimte, en werkt in O(h) tijd, waarbij h de hoogte van de boom is.