What is the expected number of nodes at depth d of a tree after i random insertions
Let $X_{d,t}$ denote the expected number of nodes at level $d$ and time $t$, and let $p_{d,t}$ be the probability that at time $t$, a node is added at level $d$. Our indexing is such that $p_{0,0} = X_{0,t} = 1$. Clearly
$$ X_{d,t} = \sum_{s=0}^t p_{d,t}. $$
Suppose that at time $t-1$, the number of leaves at depth $d-1$ is $X$. Then the probability that at time $t$ a leaf is added at depth $d$ is $X/t$. The expectation of this across the first $t-1$ steps is exactly $X_{d-1,t-1}$, and so
$$ p_{d,t} = \frac{X_{d-1,t-1}}{t}. $$
Therefore
$$ X_{d,t} = \sum_{s=1}^t \frac{X_{d-1,s-1}}{s}. $$
What does this look like? Let's use generating functions:
$$ P_d(z) = \sum_{t=0}^\infty X_{d,t} z^t = \sum_{t=0}^\infty \sum_{s=1}^t \frac{X_{d-1,s-1}}{s} z^t = \sum_{s=1}^\infty \frac{X_{d-1,s-1}}{s} \sum_{t=s}^\infty z^t = \sum_{s=1}^\infty \frac{X_{d-1,s-1}}{s} \frac{z^s}{1-z}. $$
Notice that
$$
\int_0^z P_{d-1}(w) dw = \sum_{s=1}^\infty X_{d-1,s-1} \int_0^z w^{s-1} dw = \sum_{s=1}^\infty X_{d-1,s-1} \frac{w^s}{s}.
$$
Therefore
$$
P_d(z) = \frac{1}{1-z} \int_0^z P_{d-1}(w) dw, \quad P_0(z) = \frac{1}{1-z}.
$$
We can calculate
$$
\begin{align*}
P_0(z) &amp;= \frac{1}{1-z} \\
P_1(z) &amp;= \frac{-\log (1-z)}{1-z} \\
P_2(z) &amp;= \frac{1}{2} \frac{\log^2(1-z)}{1-z} \\
P_3(z) &amp;= \frac{1}{6} \frac{-\log^3(1-z)}{1-z}
\end{align*}
$$
A pattern becomes apparent, and is easy to prove by induction:
$$ P_d(z) = \frac{1}{d!} \frac{\log^d (1-z)^{-1}}{1-z}. $$
We can pack all this data into a bivariate generating function:
$$ P(z,w) = \sum_{d \geq 0} X_{d,t} z^t w^d = \frac{\exp (w\log (1-z)^{-1})}{1-z} = (1-z)^{-w-1}.$$
In principle, we can compute $X_{d,t}$ asymptotically from the generating functions; but it is easier to do this directly:
$$
\begin{align*}
X_{0,t} &amp;= 1 \\
X_{1,t} &amp;= \sum_{s=1}^t \frac{1}{s} = \log t + O(1) \\
X_{2,t} &amp;= \sum_{s=1}^t \frac{\log s + O(1)}{s} = \int_1^t \frac{\log s + O(1)}{s} ds + O\left(\frac{\log t}{t}\right) = \frac{\log^2 t}{2} + O(\log t) \\
X_{3,t} &amp;= \sum_{s=1}^t \frac{\log^2 s + O(\log s)}{2s} = \int_1^t \frac{\log^2 s + O(\log s)}{2s} ds + O\left(\frac{\log^2 t}{t}\right) = \frac{\log^3 t}{6} + O(\log^2 t)
\end{align*}
$$
Generalizing, we get
$$X_{d,t} = \frac{1}{d!} \log^d t + O(\log^{d-1} t).$$
With more work, it is possible to obtain lower order terms as well, indeed a polynomial in $\log t$ followed by a Laurent series.