Самый низкий общий предок

Самый низший общий предок (принятое сокращение LCA от lowest common ancestor) вершин u и v в корневом дереве T, называется наиболее далекая от корня вершина, лежащая на обоих путях от u и v до корня.

Простейший способ найти самый низший общий предок — построить пути от u и v до корня и найти их пересечение. Этот алгоритм работает за O(h), где h — глубина дерева. Кроме того, может понадобиться препроцессинг, требующий O(n) времени, для нахождения непосредственного предка для всех вершин дерева (как правило, эта структура на дереве уже имеется).

Однако, есть более быстрые алгоритмы, требующие O(n) времени на предварительные вычисления и O(1) времени на вычисление самого низшего общего предка.