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......No
def completely_balanced_trees(node_count):
if node_count == 0:
return [None]
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.

No comments: