Nejméně společný předek ( nejnižší společný předek ) vrcholů u a v v kořenovém stromu T je vrchol nejvzdálenější od kořene stromu, ležící na obou cestách od u a v ke kořenu, tj. je předkem obou. vrcholy. Obecně přijímaná zkratka je LCA z angličtiny. nejnižší (nejméně) společný předek .
Nejjednodušší a nejnaivnější algoritmus pro nalezení nejméně společného předka je vypočítat hloubky u a v a postupně se propracovávat ve stromu od každého vrcholu, dokud nenajdete společný vrchol:
Postup LCA( u , v ): h1 := hloubka ( u ) // hloubka ( x ) = hloubka vrcholu x h2 := hloubka ( v ) zatímco h1 ≠ h2: pokud h1 > h2: u := rodič ( u ) h1 := h1 - 1 else : v := parent( v ) h2 := h2 - 1 zatímco u ≠ v : u := rodič ( u ) // rodič ( x ) = bezprostřední předek x v : = rodič ( v ) vrátit uDoba běhu tohoto algoritmu je O ( h ), kde h je výška stromu. Kromě toho může být vyžadováno předzpracování času O ( n ) k nalezení bezprostředního předka všech uzlů ve stromu (tato struktura je však ve stromu obvykle již přítomna).
Existují však rychlejší algoritmy: