## Sunday, December 21, 2008

### 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......Nodef 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.