⠀
Definition: Least Common Ancestor
Sei
ein gerichteter, azyklischer Graph.
Seienzwei Knoten. Als Least Common Ancestor (kurz LCA) von
und bezeichnen wir denjenigen Knoten , der
- sowohl Vorfahre von
als auch von ist und - unter allen gemeinsamen Vorfahren die größte Tiefe im Graphen besitzt.