In computational biology, a common way to compare two rooted trees that classify the same set L of labelled leaves is to determine the largest subset of L on which the two trees agree. In this paper we consider the size of this quantity if one or both trees are generated randomly, according to two simple null models. We obtain analytical bounds, as well as providing some simulation results that suggest a power law similar to the related problem of determining the length of the longest increasing sequence in a random permutation.