title: Enumerating ordered binary tree structures with given number of leaf nodes in python
body: <p>I need an algorithm that enumerates through all possible ordered binary trees that have a fixed number of leaf nodes.</p>
  <p>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:</p>
  <pre><code>       -
      /     \
     -       -
    / \     / \
   a   -   c   b
      / \
     d   e
  </code></pre>
  <p>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.</p>
  <p>For example:</p>
  <pre><code>get_trees_(3)
  </code></pre>
  <p>Will output:</p>
  <pre><code>(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)
  </code></pre>