Lowest common ancestor

The lowest common ancestor or least common ancestor (LCA) of a nonempty set of nodes in a rooted tree is the unique node of greatest depth that is an ancestor of every node in the set. (In biology, this corresponds to the most recent common ancestor of a set of organisms.) We will denote the LCA of a set of nodes $S = \{v_1, v_2, ..., v_n\}$ by $\operatorname{LCA}(v_1, v_2, ..., v_n)$ or by $\operatorname{LCA}(S)$.

Properties

The proofs of these properties are left as an exercise to the reader.

• $\operatorname{LCA}(\{u\}) = u$.
• If $u$ is an ancestor of $v$, then $\operatorname{LCA}(u,v) = u$.
• If neither $u$ nor $v$ is an ancestor of the other, than $u$ and $v$ lie in different subtrees of $\operatorname{LCA}(u,v)$.
• The entire set of common ancestors of $S$ is given by $\operatorname{LCA}(S)$ and all of its ancestors (all the way up to the root of the tree).
• $\operatorname{LCA}(S)$ precedes all nodes in $S$ in the tree's preordering, and follows all nodes in $S$ in the tree's postordering.
• If $S = A \cup B$ with $A$ and $B$ both nonempty, then $\operatorname{LCA}(S) = \operatorname{LCA}(\operatorname{LCA}(A),\operatorname{LCA}(B))$. For example, $\operatorname{LCA}(u,v,w) = \operatorname{LCA}(u,\operatorname{LCA}(v,w))$. (The LCA shares this property with the similar-sounding lowest common multiple and greatest common divisor.)