At any instant, every leaf node has an equal probability of splitting. So let's say initially at $t=0$ we have just 1 node. Then at $t=1$, we have 2 leaf nodes. At $t=2$ we have 3 leaf nodes with two possible tree structures. What will be the expected height of the tree at time $t=N$ with $N+1$ leaf nodes? (At any instant only one leaf node can branch into two children nodes). What will be a tight upper bound to the above expectation?
$E[H_{1}]=1$
$E[H_{2}]=2$
$E[H_{3}]=\frac{3+3+2+3+3+2}{6}=\frac{8}{3}$
