The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant 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. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.
In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from v and w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly, in constant time per query after a linear time preprocessing stage.
Read more about Lowest Common Ancestor: History
Famous quotes containing the words lowest, common and/or ancestor:
“Met face to face, these Indians in their native woods looked like the sinister and slouching fellows whom you meet picking up strings and paper in the streets of a city. There is, in fact, a remarkable and unexpected resemblance between the degraded savage and the lowest classes in a great city. The one is no more a child of nature than the other. In the progress of degradation the distinction of races is soon lost.”
—Henry David Thoreau (1817–1862)
“Just as language has no longer anything in common with the thing it names, so the movements of most of the people who live in cities have lost their connexion with the earth; they hang, as it were, in the air, hover in all directions, and find no place where they can settle.”
—Rainer Maria Rilke (1875–1926)
“We rarely quote nowadays to appeal to authority ... though we quote sometimes to display our sapience and erudition. Some authors we quote against. Some we quote not at all, offering them our scrupulous avoidance, and so make them part of our “white mythology.” Other authors we constantly invoke, chanting their names in cerebral rituals of propitiation or ancestor worship.”
—Ihab Hassan (b. 1925)