OCaml exercises

Consider a height-balanced binary tree of height h. What is the maximum number of nodes it can contain? Clearly, max_nodes = 2h - 1.

# let max_nodes h = 1 lsl h - 1;; val max_nodes: int -> int = Minimum knots

However, what is the minimum number of min_nodes? This question is more difficult. Try to find a recursive statement and turn it into a min_nodes function defined as follows: min_nodes h returns the minimum number of nodes in a height-balanced binary tree of height h.

Minimum height

On the other hand, one can ask: what are the minimum (resp. maximum) heights H of a height-balanced binary tree with N nodes? min_height (resp. max_height n) returns the minimum (resp. maximum) height of a height-balanced binary tree with n nodes.

Build trees

Now we can attack the main problem: constructing all height-balanced binary trees with a given number of nodes. hbal_tree_nodes n returns a list of all height-balanced binary trees with n nodes.

Find out how many height-balanced trees exist for n=15.

# List.length (hbal_tree_nodes 15);; - : integer = 1553 Minimum knots

The following solution follows directly from the translation of the question.

# let rec min_nodes h= if h integer =

It's not the most efficient though. Use the last two values ​​as state to avoid double recursion.

# let rec min_nodes_loop m0 m1 h= if h integer -> integer = val min_nodes: int -> int =

It is not difficult to show that min_nodes h = Fh+2‌ - 1, where (Fn) is the Fibonacci sequence.

Minimum height

By reversing the formula max_nodes = 2h - 1, we directly find that Hₘᵢₙ(n) = ⌈log₂(n+1)⌉ which is easily implemented:

# let min_height n = int_of_float(ceil(log(float(n+1))/.log 2.));; val min_height: int -> int =

Let's give a proof that the formula for Hₘᵢₙ is valid. First, if h = min_height n, there is a height-balanced tree of height h with n nodes. Thus 2ʰ - 1 = max_nodes h ≥ n i.e. h ≥ log₂(n+1). To establish the equality for Hₘᵢₙ(n), one must show that, for all n, there exists a height-balanced tree of height Hₘᵢₙ(n). This is due to the relation Hₘᵢₙ(n) = 1 + Hₘᵢₙ(n/2) where n/2 is integer division. For n odd, this is easily proved - so we can build a tree with an upper node and two subtrees with n/2 nodes of height Hₘᵢₙ(n) - 1. For n even, the same proof works if we notice first that, in this case, ⌈log₂(n+2)⌉ = ⌈log₂(n+1)⌉ — using log₂(n+1) ≤ h ∈ ℕ ⇔ 2ʰ ≥ n + 1 and the fact that 2ʰ is even for this. This makes it possible to have a subtree with n/2 nodes. For the other subtree with n/2-1 nodes, it is necessary to establish that Hₘᵢₙ(n/2-1) ≥ Hₘᵢₙ(n) - 2 which is easy because, if h = Hₘᵢₙ(n/2-1 ) , then h+2 ≥ log₂(2n) ≥ log₂(n+1).

The above function is however not the best one. This is because not all 64-bit integers can be represented exactly as a floating point number. Here's one that only uses integer operations:

# let rec ceil_log2_loop log plus1 n = if n = 1 then if plus1 then log + 1 else log else ceil_log2_loop (log + 1) (plus1 || n land 1 0) (n / 2) let ceil_log2 n = ceil_log2_loop 0 false n;; val ceil_log2_loop: int -> bool -> int -> int = val ceil_log2: int -> int =

This algorithm is still not the fastest, however. See for example Hacker's Delight, section 5-3 (and 11-4).

Following the same idea as above, if h = max_height n, then we easily deduce that min_nodes h ≤ n < min_nodes(h+1). This gives the following code:

# let rec max_height_search h n = if min_nodes h int -> int = val max_height: int -> int =

Of course, since min_nodes is calculated recursively, there is no need to recalculate everything to go from min_nodes h to min_nodes(h+1):

# let rec max_height_search h m_h m_h1 n = if m_h integer ...