99 questions/Solutions/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.

cbalTree 0 = [Empty]
cbalTree n = [Branch 'x' l r | i <- [q .. q + r], l <- cbalTree i, r <- cbalTree (n - i - 1)]
 where (q, r) = quotRem (n-1) 2

Here we use the list monad to enumerate all the trees, in a style that is more natural than standard backtracking.