Simultan cu vectorul {$level$} construim si vectorul {$low$}.
Pe baza informatiilor astfel calculate, construim un arbore cu $N$ noduri in care tatal nodului {$i$}, $i$ de la $1$ la {$N$}, va fi {$low{~i~}$}. Acum trebuie sa aflam nodul $u$ din acest arbore care indeplineste {$nivel{~u~}$} ≤ {$nivel{~L~}$} si {$u$} se afla cat mai aproape de {$x$}. Raspunsul pe query va fi dat de diferenta de nivel dintre $u$ si {$x$}.

Pentru a afla nodul $u$ in timp logaritmic ne putem intoarce pe stramosi ai lui $x$ pe baza de puteri ale lui 2 sau putem afla nodul $u$ in O(1), demonstrand ca nodul cautat $u$ este fie {$L$}, fie {$parinte{~L~}$} in acest arbore.

Pentru a afla nodul $u$ in timp logaritmic ne putem intoarce pe stramosi ai lui $x$ pe baza de puteri ale lui 2 sau putem afla nodul $u$ in {$O(1)$}, demonstrand ca nodul cautat $u$ este fie {$L$}, fie {$parinte{~L~}$} in acest arbore.

==Include(page="template/preoni-2007/footer")==