  Different sources of information might tell different stories about the
evolutionary history of a given set of species. This leads to (rooted)
phylogenetic trees that "disagree" on triples of species, which we call
"conflict triples". An important subtask of computing consensus trees which is
interesting in its own regard is the enumeration of all conflicts exhibited by
a pair of phylogenetic trees (on the same set of $n$ taxa). As it is possible
that a significant part of the $n^3$ triples are in conflict, the trivial
${\Theta}(n^3)$-time algorithm that checks for each triple whether it
constitutes a conflict, was considered optimal. It turns out, however, that we
can do way better in the case that there are only few conflicts. In particular,
we show that we can enumerate all d conflict triples between a pair of
phylogenetic trees in $O(n + d)$ time. Since any deterministic algorithm has to
spend ${\Theta}(n)$ time reading the input and ${\Theta}(d)$ time writing the
output, no deterministic algorithm can solve this task faster than we do (up to
constant factors).
