Lowest common ancestor
From Wikipedia, the free encyclopedia
This article is about lowest common ancestors in graph theory and computer science. For the common ancestor of a set of species in evolutionary trees, see most recent common ancestor. For a common ancestor of all life forms, see last universal ancestor.
Let T be a rooted tree with n nodes. The lowest common ancestor (LCA) is defined between two nodes v and w as the lowest node in T that has both v and w as descendents (where we allow a node to be a descendent of itself).
The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root.
