Here is the algorithm for finding the nearest common
ancestor of two taxa `t1`

and
`t2`

:

If

`t1`

and`t2`

have the same depth, see if they are identical. If so, the result is`t1`

.If

`t1`

and`t2`

are not at the same depth, replace the deeper with its parent and return to Step 1.At this point, we know that

`t1`

and`t2`

are at the same depth but are not the same taxon. Replace each with its parent and return to Step 1.

This procedure is guaranteed to terminate, assuming that the taxa are nodes in a tree. If all else fails, it will terminate when both taxa rise to the root.

xnomo3.py

# - - - T a x o n . n e a r e s t A n c e s t o r - - - def nearestAncestor ( self, other ): """Find the nearest ancestor of self and other. """ #-- 1 -- t1 = self t2 = other #-- 2 -- # [ return the nearest ancestor of t1 and t2 ] while t1 is not t2: #-- 2 body -- # [ if t1.rank.depth < t2.rank.depth -> # t1 := parent of t1 # else if t1.rank.depth > t2.rank.depth -> # t2 := parent of t2 # else -> # t1 := parent of t1 # t2 := parent of t2 ] if t1.rank.depth < t2.rank.depth: t2 = t2.parent elif t1.rank.depth > t2.rank.depth: t1 = t1.parent else: t1 = t1.parent t2 = t2.parent #-- 3 -- return t1