99 problems - python - 55

Construct completely balanced binary trees

In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function cbal-tree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

# Example:

# * cbal-tree(4,T). 
# T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
# T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
# etc......No
def completely_balanced_trees(node_count):
    if node_count == 0:
        return [None]
    else:
        right_count  = (node_count - 1) / 2
        left_count = (node_count - 1) - right_count
        left_trees = completely_balanced_trees(left_count)
        right_trees = completely_balanced_trees(right_count)

        trees = []
        for left in left_trees:
            for right in right_trees:
                trees.append(("x", left, right))
                if left_count != right_count:
                    trees.append(("x", right, left))

        return trees

OK, I'm using tuples for trees again. So sue me.