99 Clojure Problems – 59: Construct Height-Balanced Binary Trees

"In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.

Write a method to construct height-balanced binary trees for a given height with a supplied value for the nodes. The function should generate all solutions."

Example

ninety-nine-clojure.bintrees> (height-balanced-trees 2 'x)
([x [x nil nil] [x nil nil]] [x [x nil nil] nil] [x nil [x nil nil]])

Discussion

To get some intuition for this problem we can distinguish tree cases:

1. The left subtree has the same length as the right subtree
2. The left subtree is shorter by one level
3. The right subtree is shorter by one level

If we combine all three cases via concat we have our solution. We generate the solutions by recursively calling the function with the heights h-1 and h-2. We don't have to generate the 'short' versions of the left and right subtrees separately. We can just create both combinations (left shorter/right shorter) with just one copy of the lower subtrees (h-2) and one copy of the higher subtrees (h-1). Still, there is some redundant computation going on as the h-1 contains also the h-2 subtrees. Memoization might help here.

The practical applicability of the function just created as described is somewhat limited as the number of height balanced binary trees grows exponentially. For our test case we therefore just look at trees up to five levels high.

Read more about this series.