BinaryTrees.sagews

B0 = BinaryTree(None)
B0

.

B1 = BinaryTree([B0,B0])
B1

[., .]

latex.eval(latex(B1))

''

B2 = BinaryTree([B1,B0])
latex.eval(latex(B2))

''

︠07f55857-4737-4c79-b0ff-7e26edd4fc72s︠
B3 = BinaryTree([B0,B1])
latex.eval(latex(B3))

''

B4 = BinaryTree([B3,B2])
latex.eval(latex(B4))

''

def allBinaryTrees(n):
    result = []
    if n == 0:
        result.append(None)
        return result
    for k in range(n):
        l = n-1-k
        C = CartesianProduct(allBinaryTrees(k),allBinaryTrees(l))
        for t in C:
            result.append(BinaryTree(t))
    return result

S1 = [1,2]
S2 = [3,4]
print S1
print S2

[1, 2] [3, 4]

CartesianProduct(S1,S2)

Cartesian product of [1, 2], [3, 4]

for elt in CartesianProduct(S1,S2):
    print elt

[1, 3] [1, 4] [2, 3] [2, 4]

allBinaryTrees(2)

[[., [., .]], [[., .], .]]

allBinaryTrees(3)

[[., [., [., .]]], [., [[., .], .]], [[., .], [., .]], [[., [., .]], .], [[[., .], .], .]]

len(allBinaryTrees(4))

14

def randomBinaryTree(n):
    if n == 0:
        return BinaryTree(None)
    Cn = catalan_number(n)
    rank = randint(1,Cn)
    Card = 0
    for k in range(n):
        Card += catalan_number(k) * catalan_number(n-1-k)
        if Card >= rank:
            B1 = randomBinaryTree(k)
            B2 = randomBinaryTree(n-k-1)
            return BinaryTree([B1,B2])

randomBinaryTree(3)

[[., .], [., .]]

n = 3
d = {bt:0 for bt in BinaryTrees(n)}
for i in range(1000):
    d[randomBinaryTree(n)] +=1
print d

{[[., [., .]], .]: 189, [., [[., .], .]]: 185, [[[., .], .], .]: 202, [[., .], [., .]]: 225, [., [., [., .]]]: 199}