99 Clojure Problems – 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."

Example

>(balanced-trees 3 'x)
([x [x nil nil] [x nil nil]])

Verification

(defspec balanced-trees-are-balanced
  20
  (prop/for-all [i gen/nat]
                (->> (balanced-trees i 'x)
                     (apply  breadth-first-traverse)
                     (map balanced?)
                     (reduce #(and %1 %2)))))

Discussion

The following observations lead to a possible solution:

1. We can enumerate all the trees by combining the root node with all its possible subtrees to the left and to the right which have in sum \(n-1\) nodes
2. We distinguish between even and odd values of n
3. Odd values of n give balanced trees as \(n-1\) is even and both subtrees will be of equal size
4. Even values of n give balanced trees if we return all combinations of left/right trees with \((n-1) / 2\) and \((n-1) / 2 + 1\) nodes. We are using integer division here, thereby effectively 'flooring' and 'ceiling'

Based on this understanding the implementation is fairly straightforward. We handle the base case of an empty tree separately and then the two cases for odd and even number of nodes.

There is a little bit of ceremony involved in order to create the combinations of subtrees in the case of odd-sized subtrees. You have to do a nested mapcat to get both variants with the longer subtree in left and right position respectively. Maybe there is room for improvement.

I found it instructive to look at the Haskell and Prolog solutions in order to get a better understanding. The latest version of my code tries to come close to the clarity of the Prolog solution.

Read more about this series.