  A central theme in phylogenetics is the reconstruction and analysis of
evolutionary trees from a given set of data. To determine the optimal search
methods for reconstructing trees, it is crucial to understand the size and
structure of the neighbourhoods of trees under tree rearrangement operations.
The diameter and size of the immediate neighbourhood of a tree has been
well-studied, however little is known about the number of trees at distance
two, three or (more generally) $k$ from a given tree. In this paper we provide
a number of exact and asymptotic results concerning these quantities, and
identify some key aspects of tree shape that play a role in determining these
quantities. We obtain several new results for two of the main tree
rearrangement operations - Nearest Neighbour Interchange and Subtree Prune and
Regraft -- as well as for the Robinson-Foulds metric on trees.
