Expectation for the number of leaf nodes in a randomized tree construction
I tried to define a random variable $x_i$ for a node $i$, which is $1$ if it is a leaf node and $0$ otherwise. 

Then, I must find $$E(X) = \sum_i E(x_i)$$. 

If $A_{ij}$ shows the event that the node $j$ is connected to the node $i$, then I must have $\bar A_{ij}$, and then $Pr[x_i = 1] = Pr[\bar A_{ii+1}].Pr[\bar A_{ii+2} | \bar A_{ii+1}]....$

$j$ must be bigger than $i$, pointing to the nodes that arrive after the node $i$. Let $j$ be $i+1$.

$$Pr[A_{ij}] = \frac{1}{j-1}$$ so $$Pr[\bar A_{ij}] = 1- \frac{1}{j-1} = \frac{j-2}{j-1}$$

The reason is that when the node $j$ arrives there are $j-1$ nodes to be attached to. Similarly:

$$Pr[\bar A_{ij+1} | \bar A_{ij}] = 1 - \frac{1}{j} = \frac{j-1}{j}$$

so 

$$Pr[\bar A_{in} | \bar A_{ij} \cap \bar A_{ij+1} ... \cap \bar A_{in-1} ] = 1- \frac{1}{n-1} = \frac{n-2}{n-1}$$

So, let's multiply them to each other:

$$ Pr[x_i = 1] = \frac{j-2}{j-1} . \frac{j-1}{j} .. \frac{n-2}{n-1} $$

Since the product is telescopic, we have:

$$ Pr[x_i = 1] = \frac{j-2}{n-1} $$

By replacing $j$ with $i+1$:

$$  E(x_i) = Pr[x_i = 1] = \frac{i-1}{n-1}$$

So
$$ E(X) = \sum_{i=1}^{n}E(x_i) = \sum_{i=1}^{n}\frac{i-1}{n-1} = \frac{1}{n-1}\frac{n(n-1)}{2} = \frac{n}{2}$$