Lowest common ancestor

Who is more closely related to a human, a mouse or a cow? The answer lies in a tree: each pair of species has a deepest common branch from which their lines diverged, and the deeper it is, the closer the kinship. Below is the tree of life from the NCBI taxonomy: all 5931 mammal species with their ancestors and a dozen landmarks from the rest of life, 7865 vertices. Choose a pair, and the tree will show the common ancestor.

The common ancestor of human and mouse is Euarchontoglires, at depth 21. Of human and cow, Boreoeutheria, at depth 20, one level higher. The mouse is more closely related to us, although both are exactly 18 steps away along the tree. The whale is closer to the cow than to the horse: the common ancestor of whale and cow is Artiodactyla, of whale and horse Laurasiatheria. The coelacanth is closer to humans than to the zebrafish, and baker’s yeast closer to humans than to any plant: its common ancestor with us is Opisthokonta, and with thale cress only Eukaryota.

The idea

The lowest common ancestor of two vertices of a rooted tree is the deepest vertex lying on the paths from the root to both. A vertex counts as its own ancestor, so the common ancestor of a vertex and its descendant is the vertex itself. The definition and a first application are in the article on the sparse table; here is how to find it.

The simplest way: raise the deeper vertex to the level of the other, then raise both a step at a time until they coincide. This is O(h) per question, where h is the height of the tree. For the tree of life h = 38, and the naive climb answers almost instantly. But trees can be deep: a chain of commits, the parse tree of a long expression, a recursion tree. On a path a million long each question costs a million steps.

For each vertex remember not only its parent but also its ancestors 2, 4, 8, … steps higher: up[k][v] is the ancestor 2^k steps up. The table is easy to fill: a jump of 2^k is two jumps of 2^k−1. Any distance upwards is a sum of powers of two, one jump per one bit. To find the common ancestor, raise the deep vertex to the level of the other, then try jumps from longest to shortest and jump with both only if they land on different vertices. That way both stop right under the common ancestor.

This technique is called binary lifting. In research papers the same table is called jump pointers.

How it works step by step

Two chains of ancestors, of the human and of the fruit fly, starting from “cellular organisms”. The common part runs down the middle, then the chains diverge. The human is at depth 30, the fruit fly at 38.

The difference in depth is 8, 1000 in binary, and the fruit fly jumps once, eight levels at a time. Now both are at depth 30. A jump of 32 would take both above the root, where the root is the same, and such a jump is rejected. A jump of 16 leads to different vertices, so the common ancestor is higher: jump. 8 again: different again, jump. Jumps of 4, 2 and 1 lead to the same vertex: that is a common ancestor, but maybe not the lowest, so do not jump. At the end both vertices stand at depth 6, and above them is the same parent, Bilateria, at depth 5. Three jumps and seven checks instead of 58 single steps.

Why the jumps find exactly it

The first part, raising the deep vertex by the difference in depth, works the same way: the difference splits into bits, and each one bit is one jump. If the vertices coincide after the raise, one was an ancestor of the other, and the answer is that vertex.

Two traps

Distance is not kinship. The number of steps along the tree between two species, the sum of their depths minus twice the depth of the common ancestor, is easy to take for a measure of kinship. On a taxonomy this is wrong: the levels of a taxonomy are unequal, some branches have many intermediate ranks and others few. The mouse and the cow are both 18 steps from the human, yet the mouse is closer. The whale is 12 steps from the cow and 11 from the horse, yet the cow is closer. What should be compared is the depth of the common ancestor, or better the divergence time from molecular clocks, which the taxonomy does not have at all.

A jump above the root. The table has to send a jump that goes beyond the root somewhere. If −1 is written there, the very first check up[k][-1] in Python silently takes the last element of the list, and in Go it crashes. The simplest thing is to make the root its own ancestor: a jump above the root leads to the root, it is the same for both vertices, and such a jump is simply rejected.

Code

The vertices of the tree of life lie in preorder: a parent always comes before its child. So the depths and the table are computed in one pass over the array, with no depth-first search at all. The table has as many levels as there are bits in the largest depth: for depth 38 that is six, jumps of 1, 2, 4, 8, 16 and 32.

Homo sapiens + Mus musculus: Euarchontoglires at depth 21, 18 steps apart
Homo sapiens + Bos taurus: Boreoeutheria at depth 20, 18 steps apart
Balaenoptera musculus + Bos taurus: Artiodactyla at depth 22, 12 steps apart
Balaenoptera musculus + Equus caballus: Laurasiatheria at depth 21, 11 steps apart

Two more ways

The Euler tour and the range minimum. Walk the tree depth first and write down a vertex each time you enter it or return to it: this gives a sequence of length 2n − 1. Between the first occurrences of two vertices the tour passes through their common ancestor and goes no higher, so the common ancestor is the shallowest vertex on that stretch. The minimum on a stretch of an unchanging array is given by a sparse table in O(1) after O(n log n) preparation. In detail in that article, together with a problem about the common folder of two files of this site.

Tarjan’s off-line algorithm. If all the questions are known in advance, they can be put to the tree during one walk. Go depth first; when the search closes a vertex, its subtree is merged into its parent’s set with a disjoint set union, and each set remembers its top still-open vertex. On closing vertex v, look at the questions (v, u) where u is already closed: u’s set hangs exactly on the open vertex where the paths to u and to v diverge, and that is the answer.

The answers are the same as for binary lifting. Why the top open vertex of u’s set is the common ancestor: the open vertices at the moment v is closed are the path from the root to v. The subtree of each of them, except the branches still open, was merged into it as it was closed, so the closed u lies in the set of the open vertex under which it hangs, the deepest of the open ones shared with the path to u.

What it costs

A benchmark on deep random trees: each vertex hangs on one of the three previous ones, the height is about n/2, and there are as many questions as vertices. The time includes preparation.

Climbing a step at a time grows as a square: on 10,000 vertices in Python it is 22–37 times slower than the others, on 30,000 in Go 13–26 times. The three fast methods run close together, and the order between them is decided not by O but by memory. On three hundred thousand vertices in Go binary lifting loses to the Euler tour almost threefold: its table is 18 arrays of 300,000 numbers, and each jump is an access to a random place in memory, missing the cache. The sparse table makes only two accesses per question.

Where it works

Merging branches. Git merges two branches with a three-way merge: it compares both with their common ancestor. The command git merge-base looks for the best common ancestor of two commits; according to the git documentation, one common ancestor is better than another if the other is its ancestor, and a best one is one that nothing is better than. Commit history is not a tree but a directed acyclic graph, and there can be several best common ancestors when branches were merged criss-cross; the documentation warns about this explicitly.

A document in the browser. A text selection on a page is given by two ends in the document tree, and the browser returns Range.commonAncestorContainer, the deepest node containing both ends.

Compilers. In the simple dominator algorithm of Cooper, Harvey and Kennedy (2001) the intersect function moves two “fingers” up the dominator tree being built until they meet: this is the naive search for a common ancestor, and on dominator trees, usually shallow, it is enough.

Trees of life. The nearest common taxon, the common ancestor in a phylogenetic tree, the distance between species: all are the same queries to a tree. And the common ancestor also gives the distance in any tree: the depth of u plus the depth of v minus twice the depth of their common ancestor.

History

The lowest common ancestor problem was posed by Alfred Aho, John Hopcroft and Jeffrey Ullman in 1973 (the journal version of the paper came out in 1976), and they solved it off-line in almost linear time. The off-line algorithm on disjoint sets was described by Robert Tarjan in 1979, in a work on applications of path compression. An answer in O(1) after linear preparation was obtained by Dov Harel and Tarjan in 1984; their method was simplified by Baruch Schieber and Uzi Vishkin, and in 2000 Michael Bender and Martín Farach-Colton reduced everything to the minimum on a stretch of the Euler tour; this is in the history of the sparse table. The table of power-of-two jumps is one stage of their own algorithm for the ancestor at a given level (2004); in competitive programming it is known as binary lifting.

Problems

In the first problem you walk the tree of life from one species to another and name the taxon at the k-th step: binary lifting is needed both for the common ancestor and for the step itself. In the second, on lines between towns, find the longest span on a path: the same table, only with the maximum over each jump stored beside the ancestor.