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.
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
Worked example
- Suppose the root-to-
upath is1 → 3 → 5 → 9and the root-to-vpath is1 → 3 → 6 → 10. - The shared prefix is
1 → 3, so the deepest shared node is3. - Therefore
LCA(u, v) = 3. - If
u = 3, then3itself 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 it
- 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).
Next recommended lesson
Continue through this topic with Least You Need to Know: Dummy Nodes, Head Cases, and Stable Stitching.
Least You Need to Know: Dummy Nodes, Head Cases, and Stable StitchingRelated lessons
Keep going with nearby lessons in the same topic.