Here is the algorithm for finding the nearest common
ancestor of two taxa
t2 have the same depth, see if they are
identical. If so, the result is
t2 are not at the same depth, replace
the deeper with its parent and
return to Step 1.
At this point, we know that
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.
# - - - 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