Steel and Penny [7] pointed at Doucettes unpublished work [8] which presented an algorithm for computing the quartet distance in time O(n3), where n is the number of species. Bryant et al. in [9] presented an improved algorithm which computes the quartet distance in time O(n2) for binary trees. Brodal et al. in [10] showed how to compute the quartet distance in time O(n log n) considering binary trees. For arbitrary degree trees, the quartet distance can be calculated in time O(n3) or O(n2d2), where d is the maximum degree of any node in any of the two trees, as shown by Christiansen et al. [11].