Algorithms / Lca
Least You Need to Know: Lowest Common Ancestors and Path Intersections
The lowest common ancestor of two nodes is the **deepest node lying on both root-to-node paths**. LCA problems become easy once you think in terms of path overlap rather than arbitrary tree geometry.
The least you need to know
- An ancestor of a node lies on the root-to-node path.
- The LCA is the deepest common ancestor of both targets.
- If one target is an ancestor of the other, it is the LCA.
- In rooted trees, LCAs summarize where two paths first meet from above.
- Many distance and path formulas factor through the LCA.
Key notation
LCA(u, v)
lowest common ancestor of nodes u and v
depth(x)
distance in edges from the root to x
ancestor
a node on the root-to-node path
Tiny worked example
- Suppose the root-to-`u` path is `1 → 3 → 5 → 9` and the root-to-`v` path is `1 → 3 → 6 → 10`.
- The shared prefix is `1 → 3`, so the deepest shared node is `3`.
- Therefore `LCA(u, v) = 3`.
- If `u = 3`, then `3` itself is the answer because one target can be an ancestor of the other.
Common mistakes
- Students sometimes choose the root even when a deeper common ancestor exists.
- The LCA is defined relative to a rooted tree.
- Being adjacent to both nodes is not the criterion; lying on both root paths is.
How to recognize this kind of problem
- The task asks where two nodes' paths meet.
- You need the deepest shared ancestor before paths diverge.
- Distance or path queries mention `depth(u) + depth(v) - 2 depth(LCA)`.