  We examine a discrete random recursive tree growth process that, at each time
step, either adds or deletes a node from the tree with probability $p$ and
$1-p$, respectively. Node addition follows the usual uniform attachment model.
For node removal, we identify a class of deletion rules guaranteeing the
current tree $T_n$ conditioned on its size is uniformly distributed over its
range. By using generating function theory and singularity analysis, we obtain
asymptotic estimates for the expectation and variance of the tree size of $T_n$
as well as its expected leaf count and root degree. In all cases, the behavior
of such trees falls into three regimes determined by the insertion probability:
$p < 1/2$, $p = 1/2$ and $p > 1/2$. Interestingly, the results are independent
of the specific class member deletion rule used.
