How to list all binary trees ordered by the catalan relation

Question

I am looking for an algorithm in Lisp or in pseudo-code to list all binary trees ordered by the catalan relation.

For instance I want with the input '(a b c d) get this result: (a (b (c d))) (a ((b c) d)) ((a b) (c d)) ((a (b c)) d) (((a b) c) d)

Thanks in advance for any help.

Answer 1

The Catalan numbers do not define any particular ordering of binary trees. The most common ordering is by descending lexicographic ordering of leaf depths (thus, left-heavy trees are ordered before balanced trees, which are ordered before right-heavy trees).

To obtain this ordering, you can use a recursive algorithm for trees with n leaves which, for all a+b=n, a>=1, b>=1 in descending order of a, returns all trees consisting of some left child with a leaves and some right child with b leaves. That is, you recurse on both sides, and output the Cartesian product.

Some pseudocode:

def gen_trees(a,b):
    left_trees = gen_all_trees(a)
    right_trees = gen_all_trees(b)

    trees = []
    for l in left_trees:
        for r in right_trees:
            trees.append([l,r])
    return trees

def gen_all_trees(items):
    trees = []
    if len(items) == 1:
        trees += [items[0]]
    else:
        for i in range(len(items)-1, 0,-1):
            a = items[:i]
            b = items[i:]
            trees += gen_trees(a,b)
    return trees