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.

جو کم از کم جاننا ضروری ہے

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.

اہم علامتیں

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

مختصر حل شدہ مثال

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.

عام غلطیاں

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.

اس قسم کے سوال کو کیسے پہچانیں

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)`.