Изменения

В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> > времени и за <tex>O(n)</tex> памяти.

== Сравнение с наивными реализациями ==

Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,

что так же в худшем случае работает за <tex>O(n)</tex>.

В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ <tex>h</tex>.

== См. также ==

*[[Метод двоичного подъёма]]