Lowest Common Ancestor (LCA)
Lowest Common Ancestor (LCA) 1. Definition LCA (Lowest Common Ancestor) refers to finding, in a rooted tree, the nearest (deepest) common ancestor of two given nodes x and y. Using the reference tree below as an example: LCA(5, 8) = 1 LCA(6, 10) = 3 Reference Tree 1 / \ 2 3 / | \ | \ 11 4 5 6 7 | 8 / \ 9 10 2. Naive Solution Steps:
Read note →