Cel mai apropiat strămoș comun
Într-un arbore genealogic, care este cel mai apropiat strămoș comun a doi veri? Într-un sistem de fișiere, care este cel mai adânc dosar care conține două fișiere? Problema LCA (*lowest common ancestor*) are o soluție O(h) într-un BST și una O(n) pentru orice arbore binar.
Problema
Pentru două noduri p și q, cel mai apropiat strămoș comun este nodul cel mai de jos care le are pe amândouă în subarborele lui. Un nod este considerat strămoș al lui însuși: dacă q se află sub p, răspunsul este p.
Scrie stramos_bst(radacina, p, q) pentru un BST (o buclă care coboară după valori, O(h)) și stramos(radacina, p, q) pentru un arbore binar oarecare (recursiv, O(n)). Ambele primesc valori și returnează nodul strămoș; testele afișează valoar…
- stramos_bst: dacă p și q sunt amândouă mai mici, mergi la stânga; amândouă mai mari, la dreapta; altfel întorci nodul.
- stramos: întorci nodul dacă e None, p sau q; altfel combini rezultatele din stânga și dreapta.
- Trebuie să apară: 6, 2, 4, 8, apoi 3, 5, 3.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan