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:
“You will find the most pronounced hatred of other nations on the lowest cultural levels. There is, though, a level where the hatred disappears completely and where one so to speak stands above the nations and where one experiences fortune or misfortune of a neighboring country as if they had happened to one’s own.”
—Johann Wolfgang Von Goethe (1749–1832)
“How like a prodigal doth nature seem,
When thou, for all thy gold, so common art!
Thou teachest me to deem
More sacredly of every human heart,
Since each reflects in joy its scanty gleam
Of Heaven, and could some wondrous secret show,
Did we but pay the love we owe,
And with a child’s undoubting wisdom look
On all these living pages of God’s book.”
—James Russell Lowell (1819–1891)
“I cannot yet begin to understand
Why we are proud that an ancestor knew
The crazy Poe, who was not of our kind
Bats in the belfry that round and round flew
In vapors not quite wholesome for the mind.”
—Allen Tate (1899–1979)