IV. Lowest Common Ancestor

Key: The subproblem could be defined as LCA(p, one, two), representing the LCA of one and two in the subtree rooted at p.

Basic methods:

1. Iterative reduction: LCA(a, b, c, d) → n1 = LCA(a,b) → n2 = LCA(n1, c) → LCA(n2, d) O(k*n)

2. Binary reduction: the order could be different than in iterative reduction.

n1 = LCA(a, b), n2 = LCA(c, d) res = LCA(n1, n2) O(k&n)

3. K-way reduction: LCA(p, nodes) = the LCA of all input nodes in subtree rooted at p