Lowest common ancestor

From PEGWiki
Revision as of 06:57, 9 December 2011 by Brian (Talk | contribs) (Created page with "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 ...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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