Graph Theory37 sections · 1633 units
Open in Course

Why LCA Matters

(Distance and path queries)

LCA solves a class of problems that come up constantly in tree algorithms. If you want the distance between 22 nodes, you need their LCA. The formula is: dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]. Without LCA, computing tree distances requires O(n)O(n) traversal per query.

LCA also enables path queries. To find the maximum edge weight between 22 nodes, you split the path at the LCA and query each half separately. Version control systems use LCA to find the merge base of 22 branches. In competitive programming, LCA appears in tree DP, path aggregation, and distance problems.