  Let $r$ and $d$ be positive integers with $r<d$. Consider a random $d$-ary
tree constructed as follows. Start with a single vertex, and in each time-step
choose a uniformly random leaf and give it $d$ newly created offspring. Let
${\mathcal T}_t$ be the tree produced after $t$ steps. We show that there
exists a fixed $\delta<1$ depending on $d$ and $r$ such that almost surely for
all large $t$, every $r$-ary subtree of ${\mathcal T}_t$ has less than
$t^{\delta}$ vertices.
  The proof involves analysis that also yields a related result. Consider the
following iterative construction of a random planar triangulation. Start with a
triangle embedded in the plane. In each step, choose a bounded face uniformly
at random, add a vertex inside that face and join it to the vertices of the
face. In this way, one face is destroyed and three new faces are created. After
$t$ steps, we obtain a random triangulated plane graph with $t+3$ vertices,
which is called a random Apollonian network. We prove that there exists a fixed
$\delta<1$, such that eventually every path in this graph has length less than
$t^{\delta}$, which verifies a conjecture of Cooper and Frieze.
