Chapter 96

Home

Lowest Common Ancestor (LCA)

The LCA of two nodes is the deepest node that is an ancestor of both. Naive: walk both nodes up until they meet — O(depth). For deep trees, binary lifting gives O(log N) per query.

Naive LCA (O(N) per query)

C++ — O(N) naive LCA

int lca_naive(int u, int v, vector& parent, vector& depth) {
    while (depth[u] > depth[v]) u = parent[u];
    while (depth[v] > depth[u]) v = parent[v];
    while (u != v) { u = parent[u]; v = parent[v]; }
    return u;
}
// O(N) per query — bad for many queries

Key Takeaways