# how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?

I am trying to implement the 24 Game in ansi C. This game goes as follows:

For a list of four given numbers, try to find a solution involving these four numbers, that, using addition(+), subtraction(-), multiplication(*) and division(/) ends up at 24. Each number can only appear once, but the order of the numbers might be changed of course. It is possible to use brackets to change the order of the operands (and you have to do so for many of the solutions).

I wanted to build on top of this problem, and invent a M Game, where M can be an arbitrary number, and you can give an arbitrary length N list of values.

What I know:

• Operators can be re-used multiple times in the formula. Thus, when iterating over the operators, I can just use flags to check if a certain operator should be used at a certain place.
• Numbers can only be used once. There exist great tutorials out there that explain how to permute an array until all different orders have been exhausted.

However, what I still am having trouble with, is how to decide the different combinations of operators.

Say I have a function

op(A, B)

This function is non-commutative, e.g. op(A,B) != op(B,A). Now, if I have four values, I want to know in what ways I need to combine these functions. I know that the sequence of Catalan numbers tells us how many options there are. (for four numbers, there are 5 sequences). These are:

1. op(A, op(B, op(C,D)))
2. op(op(op(A,B),C),D)
3. op(op(A,op(B,C),D))
4. op(A,op(op(B,C),D))
5. op(op(A,B),op(C,D))

Using a simple bitVector with recursion I am able to find the first four. But not the fifth, where two nodes share the same 'level'.

Is there an iterative way to test all these different options?

Or, as Ordous aptly put it:

how to enumerate/generate all possible binary trees from N leaves and N-1 nodes?

• So, your question is - how to enumerate/generate all possible binary trees from N leaves and N-1 nodes? – Ordous Oct 28 '14 at 15:16
• Yes, indeed. That might indeed be a more clear way to put it. I have updated the question title – Qqwy Oct 28 '14 at 20:00
• When worded this way, there are plenty of answers, on SO for example: Generating all possible topologies in a full binary tree having n nodes. However, this is extremely slow. If you ignore commutativity of 2 of your operators, you will have to traverse all trees, and there are a lot of them (4^N). – Ordous Oct 28 '14 at 22:17

Define a recursive function that takes an array of values and will generate a list of all the trees we want.

When the function receives just one value, it should return a list containing as it's sole element that value.

When the function receives two values, it should returns list containing as it's sole element the op of those two values in order.

When the function receives more than two values, it should keep a list to return, and iterate through the indices between the members of the array. For each index between members of the array, split the array into a left array and a right array based on the index. Recurse on these arrays, generating the list of trees for each. Then take the cross product of the lists this generated and add it to the list to return.

The way this works is that for any array of more than two values, we can split it multiple ways. For each way to split the array, there is at least one possible tree on the left side, and at least one possible tree on the right side. Each combination of possible trees on the right and left sides is a possible tree.

Edit: Here's some pseudo code (roughly Java/python):

``````List<Tree> getOpTrees(List<Value> values):
if (length(values) == 1):
return new List(new IdentityTree(values[0]))
if (length(values) == 2):
return new List(new OpTree(values[0], values[1]))
treeList = new List<Tree>()
for (index from 1 to length(values)-1):
leftList, rightList = values.split(index)
for (leftTree : getOpTrees(leftList)):
for (rightTree : getOpTrees(rightList)):