How to list all the possible binary search trees with n nodes?


I want to list all the possible binary search trees. I know that the number will be the catalan number. But i want to list them also.

Let's say that I assign letters to each position of a binary search tree as shown below

enter image description here

Then want to list all possible trees with N nodes. If N is 1, then the only possible tree is

A

If N is 2 then the possible trees are

A B
A C

If N is 3, the possible trees are

A B D
A B E
A B C
A C F
A C G

If N is 4, the possible trees are

A B D H
A B D I
... should be 12 more

Does anyone know a good algorithm that lists all the possible trees?


Answers:


A simple (naive?) approach consists in recursion. A binary tree with n nodes is a root, a binary tree with k<n nodes and another binary tree with n-1-k nodes.

Here is the Python code corresponding to my approach. You can easily sort the output if needeed.

def binary_trees(n, i=0):
    if not n:
        return [[]]
    else:
        ll=[]
        for k in range(n):
            l1 = binary_trees(k, 2*i+1)
            l2 = binary_trees(n-1-k, 2*i+2)
            for j in l1:
                for l in l2:
                    ll.append([i]+j+l)
        return ll

def numbers_to_letters(l):
    return [chr(i+ord('A')) for i in l]

print [numbers_to_letters(l) for l in binary_trees(4)]

An improvement could probably be done via DP: compute the trees of size 1, then 2, then 3… and keep them in memory for reuse instead of re-computing those every single time.