August 27, 2024
P60 - Construct height-balanced binary trees with a given number of nodes.
Consider a height-balanced binary tree of height HH. What is the maximum number of nodes it can contain? Clearly, Nmax=2H−1Nmax=2H−1. However, what is the minimum number NminNmin? This question is more difficult. Try to find a recursive statement and turn it into a function minHbalNodes that takes a height and returns NminNmin.
scala
scala> minHbalNodes(3)
res0: Int = 4
On the other hand, we might ask: what is the maximum height HH a height-balanced binary tree with NN nodes can have? Write a maxHbalHeight function.
scala
scala> maxHbalHeight(4)
res1: Int = 3
Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes.
scala
scala> Tree.hbalTreesWithNodes(4, "x")
res2: List[Node[String]] = List(T(x T(x T(x . .) .) T(x . .)), T(x T(x . T(x . .)) T(x . .)), ...
Find out how many height-balanced trees exist for N=15N=15.