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
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?
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.