Lowest Common Ancestor (LCA)

Găsirea celui mai apropiat strămoș comun într-un arbore cu rădăcină este o problemă cu mare aplicabilitate practică.

Iată un exemplu: știm că într-un arbore drumul între oricare două noduri există și este unic.

Pentru un nod dat, până unde trebuie să urcăm pe drumul spre rădăcină pentru ca apoi să coborâm spre nodul în care dorim să ajungem?

Avem algoritmi cu diverse complexități ca timp, memorie și efort de implementare, și care se bazează pe noțiuni învățate anterior.