h1. LCA: Lowest common ancestor

(Categoria _Algoritmi_, Autor _Emilian Miron_)

(Categoria _Arbori_, autor(i) _Miron Emilian_)

Problema luata in discutie este ca, avand un arbore dat, sa putem raspunde rapid la multe intrebari de genul: _"Care este stramosul comun cel mai apropiat dintre doua noduri din arbore?"_.
(toc)*{text-align:center} *Continut*

* 'Exemplu':lowest-common-ancestor#exemplu
* 'Aplicabilitate':lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lowest-common-ancestor#calcul
 
!> Lowest-common-ancestor?euler.jpg 80%!

* 'Exemplu':lca-lowest-common-ancestor#exemplu
* 'Aplicabilitate':lca-lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lca-lowest-common-ancestor#calcul

h2(#exemplu). Exemplu

!LCA-Lowest-common-ancestor?euler.jpg!
 

Pentru arborele din imagine, avem ca exemplu urmatoarele query-uri:
* $lca(2,3) = 1$

3699