In this paper, we solve the maximum agreement subtree problem for a set T of k rooted, leaf-labelled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn{3})-time dynamic programming algorithm proposed by Farach et al. [On the agreement of many trees] and Bryant [Hunting for trees, building trees and comparing trees: theory and methods in phylogenetic analysis] can be implemented in {\text{O(n}}^{\text{2}} {\text{log}}^{{\text{k - 1}}} {\text{n)}} and {\text{O(k\cdotn}}^{{\text{3 - }}\frac{1}{{k - 1}}}) using the k-dimensional binary search tree and the k-dimensional range search tree, respectively.