Difference between revisions of "Lowest common ancestor"

Revision as of 06:57, 9 December 2011

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

Difference between revisions of "Lowest common ancestor"

Revision as of 06:57, 9 December 2011

Properties

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools