Generating all possible trees of depth N?

Question

I have several different types of tree nodes, each of which may have anywhere from 0 to 5 children. I'm trying to figure out an algorithm to generate all possible trees of depth <= N. Any help here? I'm having trouble figuring out how to recursively walk the tree given that each change I make to a node may expose new subtrees (or remove old ones).

Answer 1

If the only difference between node types is the number of children, then generating every possible tree with only the node type with the greatest number of children will also generate every possible tree for any combination of nodes having equal or fewer children.

That's sort of a mouthful...

Put another way, if 5 children is the maximum, then some of the possible trees made of only 5-children nodes will have nodes that have, for example, two actual children, and three null pointers. This is practically the same as having a node with only two children.

Answer 2

You could create a function containing a for loop which adds the elements to a multidimensional array and calls that function again, until the tree is complete. I cannot provide examples since I don't know which language you prefer.

Answer 3

Here's a Python program I wrote up that I think does what you're asking. It'll return all of the possible trees given a starting node. Essentially, it boils down to a trick with bit manipulation: if a node has 5 children, then there are 2⁵ = 32 different possible subtrees as each child can independently be present or not present in a subtree.

Code:

#!/usr/bin/env python

def all_combos(choices):
    """
    Given a list of items (a,b,c,...), generates all possible combinations of
    items where one item is taken from a, one from b, one from c, and so on.

    For example, all_combos([[1, 2], ["a", "b", "c"]]) yields:

        [1, "a"]
        [1, "b"]
        [1, "c"]
        [2, "a"]
        [2, "b"]
        [2, "c"]
    """
    if not choices:
        yield []
        return

    for left_choice in choices[0]:
        for right_choices in all_combos(choices[1:]):
            yield [left_choice] + right_choices

class Node:
    def __init__(self, value, children=[]):
        self.value    = value
        self.children = children

    def all_subtrees(self, max_depth):
        yield Node(self.value)

        if max_depth > 0:
            # For each child, get all of its possible sub-trees.
            child_subtrees = [list(self.children[i].all_subtrees(max_depth - 1)) for i in range(len(self.children))]

            # Now for the n children iterate through the 2^n possibilities where
            # each child's subtree is independently present or not present. The
            # i-th child is present if the i-th bit in "bits" is a 1.
            for bits in xrange(1, 2 ** len(self.children)):
                for combos in all_combos([child_subtrees[i] for i in range(len(self.children)) if bits & (1 << i) != 0]):
                    yield Node(self.value, combos)

    def __str__(self):
        """
        Display the node's value, and then its children in brackets if it has any.
        """
        if self.children:
            return "%s %s" % (self.value, self.children)
        else:
            return str(self.value)

    def __repr__(self):
        return str(self)

tree = Node(1,
[
    Node(2),
    Node(3,
    [
        Node(4),
        Node(5),
        Node(6)
    ])
])

for subtree in tree.all_subtrees(2):
    print subtree

Here's a graphical representation of the test tree:

  1
 / \
2   3
   /|\
  4 5 6

And here's the output from running the program:

1
1 [2]
1 [3]
1 [3 [4]]
1 [3 [5]]
1 [3 [4, 5]]
1 [3 [6]]
1 [3 [4, 6]]
1 [3 [5, 6]]
1 [3 [4, 5, 6]]
1 [2, 3]
1 [2, 3 [4]]
1 [2, 3 [5]]
1 [2, 3 [4, 5]]
1 [2, 3 [6]]
1 [2, 3 [4, 6]]
1 [2, 3 [5, 6]]
1 [2, 3 [4, 5, 6]]

If you'd like I could translate this into a different language. You didn't specify so I used Python; the code would be a bit more verbose in Java or C++ or whatever since I took advantage of Python's list comprehensions in a big way.

Answer 4

http://books.google.co.uk/books?id=56LNfE2QGtYC&pg=PA23&lpg=PA23&dq=hansel%27s+algorithm&source=bl&ots=vMbfFj-iZi&sig=E0cI5XhVZ3q1Lg9eAJ_1zYQm53U&hl=en&ei=8udlStuKJ8ehjAfJ1ZSUAQ&sa=X&oi=book_result&ct=result&resnum=1