What is average tree size? Suppose that you generate a sequence which stops with prob q at every step or proceeds with prob p. That is you will get bernulli sequence 0 or 10 or 110 or 11...10 with corresponding lengths 1, 2, 3, ... and probabilities $q$, $pq$, $p^2q$, ... 
This is a geometric series with average length of $E[len] = 1*q + 2*pq + 3p^2q + \cdots = 1/q$. That is, if prob of failure is 1/5 then we normally will generate 5-digit lists with 5 trials.
Let the randomly generated list be 

Now, suppose that 1-labeled nodes, which are considered "real" or "non-terminal", will also have children subtree. That is, once you have generated a list with method above, you generate another list below every 1-node. An example tree generated after the root node above would be (yes, we consider that 3-element list above as a "root") 

You see that, in addition to having potentially long nodes, the trees may descend inifnitely downwards. How many trials do we need to generate such a tree?
My simulation experiment demonstrates that the tree blows up at $p \geq 1/2$. That is, random tree generator never ends at such prob of spawning a node. I am curious to know the analytic solution, dependence of avg tree size on p.
 A: For each node in your tree you have one child with probability $p$ and 0 with probability $q = 1-p$.  Let $X$ be the random variable denoting the number of nodes (including leaves) in your tree.
If the first node has no children then the tree has one node.  If it has two children then the two subtrees are independent and have the same distribution as the original tree. Therefore, conditioned on the first node having two children, the expected number of nodes in the tree is $1 + 2 \mathbb E(X)$ (one original node plus the two subtrees).
Therefore we may write
$$\mathbb E(X) = q + p(1+2\mathbb E(X))$$
which we may rearrange to get
$$\mathbb E(X) = \frac 1{1 - 2p}$$
as long as $2p < 1$.  If $2p \geq 1$ there are no positive real solutions and the tree has infinite expected value.
A: A related problem is finding the average depth of such a tree. 
Note that if you clip all the leaf nodes in your tree (of which there are n = E(X) = 1/(1-2p) on average), you will get an ordinary binary tree of size n/2 (with 0 1 or 2 children for each node instead of 0 or 2.) 
The number of such trees is the Catalan number C((n-1)/2), and the expected depth of the tree grows as ~sqrt(n/2) = O(sqrt(1-2p)). (Trees of other depth have exponentially decaying probability, so it is safe to expect tree size roughly equal to the expected tree size.)
