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:
“A lover’s eyes will gaze an eagle blind.
A lover’s ear will hear the lowest sound.”
—William Shakespeare (1564–1616)
“That we can come here today and in the presence of thousands and tens of thousands of the survivors of the gallant army of Northern Virginia and their descendants, establish such an enduring monument by their hospitable welcome and acclaim, is conclusive proof of the uniting of the sections, and a universal confession that all that was done was well done, that the battle had to be fought, that the sections had to be tried, but that in the end, the result has inured to the common benefit of all.”
—William Howard Taft (1857–1930)
“In the core of God’s abysm,—
Was a weed of self and schism;
And ever the Daemonic Love
Is the ancestor of wars,
And the parent of remorse.”
—Ralph Waldo Emerson (1803–1882)