Module algorithms_edu::algo::graph::tree::lca

Implementation of finding the Lowest Common Ancestor (LCA) of a tree. This impl first finds an Euler tour from the root node which visits all the nodes in the tree. The node height values obtained from the Euler tour can then be used in combination with a sparse table to find the LCA in O(1).

Resources

• W. Fiset's video

Structs

LcaSolver
MinSparseTable
Tree