# 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

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.