  A consensus tree is a phylogenetic tree that captures the similarity between
a set of conflicting phylogenetic trees. The problem of computing a consensus
tree is a major step in phylogenetic tree reconstruction. It also finds
applications in predicting a species tree from a set of gene trees. This paper
focuses on two of the most well-known and widely used oconsensus tree methods:
the greedy consensus tree and the frequency difference consensus tree. Given
$k$ conflicting trees each with $n$ leaves, the previous fastest algorithms for
these problems were $O(k n^2)$ for the greedy consensus tree [J. ACM 2016] and
$\tilde O(\min \{ k n^2, k^2n\})$ for the frequency difference consensus tree
[ACM TCBB 2016]. We improve these running times to $\tilde O(k n^{1.5})$ and
$\tilde O(k n)$ respectively.
