import scipy.misc
import random

# generate binary trees with the specification T = E + ZT^2
# the number of such trees of size n is binom(2n,n)/(n+1)

def genTree(n):
    # handle union
    if n==0:
        return 'E'

    #set up
    Bn = scipy.misc.comb(2*n,n)/(n+1)
    x = random.random()
	
    # now work with n-1 in the while loop for the product T^2
    k = 0
    s = (scipy.misc.comb(2*k,k)/(k+1)
         * scipy.misc.comb(2*(n-k-1),n-k-1)/(n-k))/Bn
    while x > s:
	k = k+1
	s = s + (scipy.misc.comb(2*k, k)/(k+1)
                 * scipy.misc.comb(2*(n-k-1), n-k-1)/(n-k))/Bn
    return ['Z', genTree(k), genTree(n-k-1)]

print genTree(3)
print genTree(10)
#print genTree(500)