99 questions/Solutions/55
< 99 questions | Solutions
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
(**) 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.