Problem. Given a binary tree and two nodes p and q in it, return their lowest common ancestor (LCA): the deepest
node that has both as descendants. A node counts as a descendant of itself.
3
/ \
5 1 LCA(5, 1) = 3
/ \ / \ LCA(5, 4) = 5 (5 is an ancestor of 4, and of itself)
6 2 0 8 LCA(6, 4) = 5
/ \
7 4
The new idea: a recursive call can return "what I found" (nothing, p, q, or the answer) rather than a number, and the first node where both sides report something is where p and q's paths meet.
ML context. Labels are often hierarchical: ImageNet classes sit in WordNet, products in a category tree, diagnoses in ICD codes. Confusing a terrier with a beagle (LCA: "dog") is a milder error than confusing it with a truck (LCA: "entity"). The depth of the LCA, or the tree distance through it, measures mistake severity and powers hierarchical metrics and losses (Change D).