Help:=proc(): print(`CBT(k), cbt(k), LC(p), RCBT(p,k,Sad, Happy)`): 
print(`RCBTH(k)`):
end:

#CBT(k): the set of complete binary trees with k leaves
#(and k-1 inernal vertices)
CBT:=proc(k) local S,i,S1,S2,s1,s2:
option remember:

if k=1 then
 RETURN({ []}):
fi:

S:={}:


for i from 1 to k-1 do
 S1:=CBT(i):
 S2:=CBT(k-i):

  S:= S union {seq(seq( [s1 , s2], s1 in S1), s2 in S2)}: 

od:

S:

end:

#cbt(k): the set of complete binary trees with k leaves
#(and k-1 inernal vertices)
cbt:=proc(k) local i:
option remember:

if k=1 then
 RETURN(1):
fi:

add(cbt(i)*cbt(k-i),i=1..k-1):

end:


#LC(p): a loaded coin prob. p of success(1) , 1-p failure (0)
LC:=proc(p) local a,b,ra,r:
a:=numer(p):
b:=denom(p):
ra:=rand(1..b):

r:=ra():

if r<=a then
 1:
else
 0:
fi:

end:


#RCBT(p,k,Sad, Happy) : a random complete binary tree with prob. of having kids
#=p, with <=k leaves
RCBT:=proc(p,k,Sad,Happy) local IV,LL,DL,c,leaf,g:

LL:={1}:
c:=1:
DL:={}:

IV:={}:

while (LL<>{} and nops(DL)+nops(LL)<=k) do
 
leaf:=LL[1]:

g:=LC(p):

LL:=LL minus {leaf}:

if g=0 then
 DL:=DL union {leaf}:
else
  IV:=IV union {[leaf,  [c+1,c+2 ] ] }:

  LL:=LL union {c+2,c+1}:

   c:=c+2:
fi:


od:


if LL={} then
 RETURN(Sad):
else
 RETURN(Happy):
fi:

end:



#RCBTH(k) : a random complete binary tree with prob. of having kids
#=p, with <=k leaves
RCBTH:=proc(k) local IV,LL,DL,c,leaf,g,p:

p:=1/2:
LL:={1}:
c:=1:
DL:={}:

IV:={}:

while (LL<>{} and nops(DL)+nops(LL)<=k) do
 
leaf:=LL[1]:

g:=LC(p):

LL:=LL minus {leaf}:

if g=0 then
 DL:=DL union {leaf}:
else
  IV:=IV union {[leaf,  [c+1,c+2 ] ] }:

  LL:=LL union {c+2,c+1}:

   c:=c+2:
fi:


od:


if LL={} then
 RETURN(nops(DL)):
else
 RETURN(FAIL):
fi:

end: