Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees

The reconstruction of an ultrametric tree from a distance matrix is a very frequent subproblem in clustering or reconstructing evolutionary trees, both are common problems in Bioinformatics. In his famous book, Gusfield presented a very simple, but not time-optimal recursive algorithm for this problem. We show that a simple modification of Gusfield's algorithm allows a time-optimal solution.