Consider this procedure for building a tree from $ v_1, v_2, …, v_n$ :

- insert $ v_1$
- insert $ v_2$ and connect it to $ v_1$ via a directional edge from $ v_2$ to $ v_1$
- insert $ v_3$ and with a uniform probabiliy connect to $ v_1$ or $ v_2$
- …
- insert $ v_n$ and with a uniform porability connect it to $ v_1$ or $ v_2$ ,… $ v_{n-1}$

The question is what is the expectation for the number of leaf nodes? Those with no other node connected to them.

**My effort**: I tried to define a random variable $ x_i$ for a node $ i$ , which is 1 if it is leaf and 0 otherwise. Then I must find $ E(X) = \sum_i E(x_i)$ . However, finding the probability of $ Pr[x_i =1]$ isn’t that easy. I guess it must be a conditional probability, which guarantees no node with be added to $ x_i$ as we insert new nodes. If $ A_{ij}$ shows the event that node $ j$ is connected to node $ i$ , then I must have $ \bar A_{ij}$ and then $ Pr[x_i == 1] = Pr[\bar A_{ij}].Pr[\bar A_{ij+1} | \bar A_{ij}]….$

However, I’m not sure about my analysis and about the solution for it.

Could you please guide me?