We present a fast algorithm for computing the quartet distance between trees of arbitrary degree. Given input trees T and T', the algorithm runs in time O(n + |V|·|V'| min{id, id'}) and space O(n + |V|·|V'|), where n is the number of leaves in the two trees, V and V are the non-leaf nodes in T and T', respectively, and id and id' are the maximal number of non-leaf nodes adjacent to a non-leaf node in T and T', respectively. The fastest algorithms previously published for arbitrary degree trees run in O(n3) (independent of the degree of the tree) and O(|V|·|V'|·id·id'), respectively. We experimentally compare the algorithm with existing algorithms for computing the quartet distance for general trees.