5
$\begingroup$

Assuming that you start out with a root node, and decide with 50% probability whether or not to add two children nodes. If they do, repeat this process for them. How can you find the average length of this random binary tree?

I'm thinking along the lines of

$\displaystyle\lim_{n\to\infty}\sum\limits_{i=1}^n (\frac{n}{2})^2$.

because 1/2 * n represents 50% probability, and I'm squaring it because the tree gets exponentially larger. However, I feel like I've done something terribly wrong (probably because I have). Can anyone give me some help?

  • 2
    So you would expand your graph 'breadth-first', one generation at a time and the 'length' is the number of the last generation before it dies? Intuitively it seems the $n+1$'th generation would have $2\cdot\tfrac{1}{2}$ times as many nodes as the $n$'th so there would 'on average' be infinitely many generations. But that's just silly intuition.2011-03-03
  • 1
    @Myself: That was my feeling too, that the "average" diverges. Lets see if a proof presents itself.2011-03-03
  • 0
    @Eric and @Myself are correct that the expected number of nodes is 1 in each generation, but that need not always imply an infinite expected height. To take a different example, suppose that each entire generation either doubled or was wiped out, then the expected number of nodes in each generation would be 1 *ad infinitum* but the expected number of generations would be 1.2011-03-03

3 Answers 3