99 Clojure Problems – 60: Construct Height-balanced Binary Trees with a Given Number of Nodes.

"Construct height-balanced binary trees with a given number of nodes. Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain? Clearly, MaxN = 2H - 1.

However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a function min-hbal-nodes that takes a height and returns MinN.

On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have?

Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes."

Example:

ninety-nine-clojure.bintrees> (min-hbal-nodes 4)
7
ninety-nine-clojure.bintrees> (all-hbal-trees 4 'x)
([x [x [x nil nil] nil] [x nil nil]] [x [x nil nil] [x [x nil nil] nil]] [x [x nil [x nil nil]] [x nil nil]] [x [x nil nil] [x nil [x nil nil]]])

Discussion

The solution to problem 60 builds upon the solution to problem 59, so if you have not done that one yet, now would be a good time.

As always I don't want to give away the solution in the blog post right away to give you a chance to try it yourself first. But if you get stuck, it is all on Github.

Approach

The question contains a hint towards a possible solution but it was not immediately clear to me how the minimum number of nodes at a given height MinN helps us in finding all height-balanced trees with a given number of nodes.

It helped me to explore the problem starting with the expected result and progressing to the intermediate computations mentioned in the problem description later: What do we want to achieve and which parts do we have already?

1. We have a method "height-balanced-trees" to calculate all height-balanced trees with a certain height from P59.
2. We could now just filter the result of calling this existing function, leaving those trees in the result that have the required number of nodes and have the desired solution to problem 60.
3. But at which height do we start generating trees and where do we stop? We cannot generate trees for all possible heights.
4. Working our way back towards the beginning of the question, we could use the maximum height H of a tree with a given number of nodes as the upper bound of the input to the "height-balanced-trees" function from problem 59.
5. That leaves us with the missing lower bound: What is the minimum height of a tree with a given number of nodes? We need another function to answer that question. Let's start with that one.

Minimum Height of a Tree with a Given Number of Nodes

If we recursively half the given number of nodes and keep track of how many times we did that we have the minimum height, because it is a height-balanced binary tree. But we could also exploit the fact that the height of a balanced binary tree of n nodes is log2 n + 1.

Maximum Height of a Tree with a Given Number of Nodes

Now this part is a bit trickier. We now need to know what the minimum number of nodes at a given height is, as indicated in the question. Why? Let's look at the number of nodes for all the trees at a given height:

H=3: (4 5 6 7)
H=4:       (7 8 9 10 11 12 13 14 15)
H=5:                   (12 13 14 15 16 17 18 19 20 ...

To pick an interesting example: A tree with seven nodes is at most four levels high. We know that because the minimum number of nodes at height five is greater than seven. If we look at all MinN for increasing heights and stop when MinN gets bigger then our N, we know that the previous height is the maximum height we are looking for.

Now how do we calculate the MinN? Interestingly the MinN(H) is always the MinN(H-1) + MinN(H-2) +1. A formula that seems like a twist on the Fibonacci sequence. I don't have a good intuition as to why this is, but you can just derive this rule by looking at trees with small Hs.

The mentioned formula translates nicely into a recursive function.

Solution and Outlook

Putting it all together is then relatively straight forward. So much so that I will share the code right here:

(defn all-hbal-trees
  "P60 (**)  ... Now, we can attack the main problem: construct all the
  height-balanced binary trees with a given nuber of nodes."
  [n v]
  (->>  (range (min-height-hbal n) (inc (max-height-hbal n)))
        (mapcat #(height-balanced-trees % v))
        (filter #(= n (num-nodes %)))))

Reusing the code from problem 59 is certainly nice but this solution seemed rather wasteful to me as we are throwing away many intermediate results in the filter step. Feeling a bit underwhelmed by my solution I started exploring the original Prolog solution to the problem and reimplemented it using David Nolen's core.logic library. We will cover this additional experiment in the next post.

Read more about this series.