Editing 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 <math>S = \{v_1, v_2, ..., v_n\}</math> by <math>\operatorname{LCA}(v_1, v_2, ..., v_n)</math> or by <math>\operatorname{LCA}(S)</math>.

==Properties==
''The proofs of these properties are left as an exercise to the reader.''
* <math>\operatorname{LCA}(\{u\}) = u</math>.
* If <math>u</math> is an ancestor of <math>v</math>, then <math>\operatorname{LCA}(u,v) = u</math>.
* If neither <math>u</math> nor <math>v</math> is an ancestor of the other, than <math>u</math> and <math>v</math> lie in different subtrees of <math>\operatorname{LCA}(u,v)</math>.
* The entire set of common ancestors of <math>S</math> is given by <math>\operatorname{LCA}(S)</math> and all of its ancestors (all the way up to the root of the tree).
* <math>\operatorname{LCA}(S)</math> precedes all nodes in <math>S</math> in the tree's preordering, and follows all nodes in <math>S</math> in the tree's postordering.
* If <math>S = A \cup B</math> with <math>A</math> and <math>B</math> both nonempty, then <math>\operatorname{LCA}(S) = \operatorname{LCA}(\operatorname{LCA}(A),\operatorname{LCA}(B))</math>. For example, <math>\operatorname{LCA}(u,v,w) = \operatorname{LCA}(u,\operatorname{LCA}(v,w))</math>. (The LCA shares this property with the similar-sounding [[lowest common multiple]] and [[greatest common divisor]].)