0

I need an algorithm that enumerates through all possible ordered binary trees that have a fixed number of leaf nodes.

Allow me to illustrate. Imagine you have n different variables. You now want to know which values you can get by subtracting them from each other in different orders. One such value could be (n=5): ((a - (d - e)) - (c - b)), which would be represented by this binary tree:

       -
    /     \
   -       -
  / \     / \
 a   -   c   b
    / \
   d   e

So what I now need is an algorithm to generate all of these trees. I could also work with an algorithm that only generates the different structures, because I could then pretty easily insert the variables into the leaves. Remember that it has to be ordered, so for example, (a - (b - c)) != (a - (c - b)). Just like with subtraction.

For example:

get_trees_(3)

Will output:

(a,(b,c))
(a,(c,b))
(b,(a,c))
(b,(c,a))
(c,(a,b))
(c,(b,a))
((b,c),a)
((c,b),a)
((a,c),b)
((c,a),b)
((a,b),c)
((b,a),c)
Truls Henriksson
  • 51
  • 7
  • It can be done with a simple permutation, and you may group the nodes for each option – nagyl Aug 20 '20 at 18:52
  • It's not quite that simple. Note that `((c, a), b)` and `(c, (a, b))` are two distinct trees, even though the left-to-right ordering of the leaves is the same in each. – chepner Aug 20 '20 at 18:54

0 Answers0