Enumerate all full (labeled) binary tree

Question

I'm searching a practical algorithm for enumerating all full labeled binary tree.

A full binary tree is a tree where all internal nodes has a degree 3, the leaves has degree 1 and the root has a degree 2.

A labeled tree is a tree where all leaves has a unique label.

Example:

    *
    |\
    | \
    *  *
   /|  |\
  / |  | \
 T  C  D  F

Aren't you just looking for a tree traversal algorithm? http://en.wikipedia.org/wiki/Tree_traversal — domino, Feb 15 '13 at 18:09
@domino Traversal enumerates the nodes of a single tree, not a set of trees. — us2012, Feb 15 '13 at 18:10
Do you want to print just the leaves? Can you give an example of what the output would be for that tree? — pcalcao, Feb 15 '13 at 18:20
That's not the traversal. I want to generate all possible trees with n leaves. — Giggi, Feb 15 '13 at 18:29
@ pcalcao any format that describe the full structure of the tree. The newick format is probably the better choose. — Giggi, Feb 15 '13 at 18:34

rici · Accepted Answer · 2013-02-16T05:54:30.627

From comments, it is clear that the question is to enumerate rooted unordered labelled full binary trees. As explained in this paper, the number of such trees with n labels is (2n-3)!! where !! is the double factorial function.

The following python program is based on the recursive proof in the referenced paper; I think the code is straight-forward enough that it will pass as an explanation of the algorithm:

# A very simple representation for Nodes. Leaves are anything which is not a Node.
class Node(object):
  def __init__(self, left, right):
    self.left = left
    self.right = right

  def __repr__(self):
    return '(%s %s)' % (self.left, self.right)

# Given a tree and a label, yields every possible augmentation of the tree by
# adding a new node with the label as a child "above" some existing Node or Leaf.
def add_leaf(tree, label):
  yield Node(label, tree)
  if isinstance(tree, Node):
    for left in add_leaf(tree.left, label):
      yield Node(left, tree.right)
    for right in add_leaf(tree.right, label):
      yield Node(tree.left, right)

# Given a list of labels, yield each rooted, unordered full binary tree with
# the specified labels.
def enum_unordered(labels):
  if len(labels) == 1:
    yield labels[0]
  else:
    for tree in enum_unordered(labels[1:]):
      for new_tree in add_leaf(tree, labels[0]):
        yield new_tree

For n == 4, there are (2*4 - 3)!! == 5!! == 1 * 3 * 5 == 15 trees:

>>> for tree in enum_unordered(("a","b","c","d")): print tree
... 
(a (b (c d)))
((a b) (c d))
(b (a (c d)))
(b ((a c) d))
(b (c (a d)))
(a ((b c) d))
((a (b c)) d)
(((a b) c) d)
((b (a c)) d)
((b c) (a d))
(a (c (b d)))
((a c) (b d))
(c (a (b d)))
(c ((a b) d))
(c (b (a d)))

Another possible interpretation of the question was that it sought an enumeration of rooted ordered full binary trees with a specified list of labels. The number of such trees with n leaves is given by C_n-1, from the Catalan number sequence.

def enum_ordered(labels):
  if len(labels) == 1:
    yield labels[0]
  else:
    for i in range(1, len(labels)):
      for left in enum_ordered(labels[:i]):
        for right in enum_ordered(labels[i:]):
          yield Node(left, right)

For 5 labels, we have C_5-1 == 14:

>>> for tree in enum_ordered(("a","b","c","d", "e")): print tree
... 
(a (b (c (d e))))
(a (b ((c d) e)))
(a ((b c) (d e)))
(a ((b (c d)) e))
(a (((b c) d) e))
((a b) (c (d e)))
((a b) ((c d) e))
((a (b c)) (d e))
(((a b) c) (d e))
((a (b (c d))) e)
((a ((b c) d)) e)
(((a b) (c d)) e)
(((a (b c)) d) e)
((((a b) c) d) e)

This looks like a great way to get all binary *search* trees. I'm wondering if that's what the OP's question is. — templatetypedef, Feb 15 '13 at 19:04
@templatetypedef: OP says "complete binary trees", and that's what I've produced. A BST has labeled nodes as well as labeled leaves, and is not necessarily complete (a node can have just one child). — rici, Feb 15 '13 at 19:05
Sorry.. but your code enumerate only (A (B C)) ((A B) C) And not ((A C) B) — Giggi, Feb 15 '13 at 19:56
@giggi: if you want all possible label sequences, call enum with every permutation of the labels. That will be impractically many trees, though. — rici, Feb 15 '13 at 20:07
@ rici That's not true, If I use all permutations I generate a lot of isomorphic tree, for example (A (B c)) and ((B c) A) or ((C B) A) .... — Giggi, Feb 15 '13 at 20:27
@Giggi: fair enough. I added an algorithm which should work, but I don't know how to verify it. — rici, Feb 15 '13 at 22:16
I was going to ask a followup for an unrooted tree of *m* nodes, but I realized that this is equivalent to a rooted tree of *m-1* nodes so your code works. (Just choose one node and always consider it as being attached at the root.) — Quantum7, Dec 07 '17 at 14:14
Hello, I will be interested to use this code to generate the 105 different rooted trees for 5 leaves. However I am not sure how to run as in the example indicated n == 4. Do I change the values within the code? thx — Nico64, Jun 25 '20 at 17:23
@Nico64: If you supply four labels, then you have n==4. If you supply five labels, you have n==5. You don't have to change anything. Just call the function with the list of labels, as in the examples provided. — rici, Jun 25 '20 at 18:32

Enumerate all full (labeled) binary tree

1 Answers1

Linked

Related