Number of balanced binary trees (The Art of Computer Programming)

In the section 6.2.3 (Volume 3) Donald Knuth says:

... we can ask about the number $B_{nh}$ of balanced binary trees with $n$ internal nodes and height $h$. It is not difficult to compute the generating function $B_h(z) = \sum_{n\ge0} B_{nh}z^n$ for small $h$, from the relations

$$B_0(z) = 1,$$ $$B_1(z) = z,$$ $$B_{h+1}(z) = zB_h(z)(B_h(z) + 2B_{h-1}(z)).$$

I would understand this formulas if they were like this:

$$B_0 = 1$$ $$B_1 = 1$$ $$B_{h+1} = B_hB_h + B_hB_{h-1}+B_{h-1}B_h = B_h(B_h + 2B_{h-1})$$

Which means that there is only one empty tree ($h=0$), only one tree with a single node ($h = 1$) and number of other trees (of $h+1$, where $h\ge1$) can be calculated as the number of all combinations of shorter trees - having trees shorter by one on as both sub-trees ($B_hB_h$), having shorter by one on the left and shorter by two on the right ($B_hB_{h-1}$) and the wise versa ($B_{h-1}B_h$).

These formulas are actually the same as the ones from the book if $z=1$. This makes me think that it is correct.

Is my reasoning correct? And if it is, can anyone explain what this $z$ actually stands for?

The way I tend to interpret these parameters is to think of them as stand-ins for some type of basic structure in your enumeration problem. This might sound a bit too abstract, so let's look at a (simpler) concrete example.

Let's consider the task of enumerating linked lists. The question I'm interested in is, given a list of unit types (those whose only element is the unit $\circ$), how many lists over unit are there such that their length is $n$? Now, this question was chosen for a very simple purpose: it's easy to see what the answer is. If each element of your list can only be a single element $\circ$, then obviously there's exactly one list of size $n$.

Now, one way to solve this is to look at the inductive definition of a list.
$$
\textrm{List}_{\circ} = \circ :: \textrm{List}_{\circ} ~\textrm{or}~ []
$$

This says that a list over $\circ$ is either a $\circ$ prepended to another list, or it is an empty list. Flattening out the fancy operators into tuple form, and turning the word $\rm or$ into a $+$, we have

$$
\textrm{List}_{\circ} = (\circ * \textrm{List}_{\circ}) + []
$$

Since an empty list [] can be thought of as a tuple with zero $\circ$s inside, let's rewrite it as $\circ^0 = 1$. This then gives an equation

$$
L = \circ * L + 1
$$

Suppose that we're working over the complex field, then this is equivalent to (assuming that $\circ \ne 1$)
$$
L = \frac{1}{1 - \circ} = \circ^0 + \circ^1 + \circ^2 + \circ^3 + \dots
$$

Now, notice that the formal power series of $L$ with respect to $\circ$ exactly specifies all of the possible lists over the unit $\circ$. That's kind of cool, but is it just a coincidence?

To find out, we turn our attention to a related problem, that of counting lists over the booleans $(\bot, \top)$. Once again, we start with the inductive definition

$$
\textrm{List}_{2} = (\bot ~\textrm{or}~ \top) :: \textrm{List}_{2} ~\textrm{or}~ []
$$

Doing the same transformation as before, we find that

$$
L_2(\bot, \top) = \frac{1}{1 - (\bot + \top)} = 1 + \bot + \top + \bot^2 + \bot\top + \top\bot + \top^2 + \bot^3 + \bot^2\top + \dots
$$

Interesting, it seems like for certain enumeration problems, the inductive definition we use to specify/construct a type can be translated into this functional over the complex numbers. What's more, this functional's formal power series seems to generate a series of constructions that are isomorphic to the objects from your inductive specification. This is more or less the idea behind these generating functions: their series representation "generates" the combinatorial structures that you are studying.

Now, let's come back to the counting problem. So what if we know that $\frac{1}{1 - \top - \bot}$ represents our combinatorial class? How does this help us with the enumeration problem? Well, the counting problem asks for the number of lists that contains a certain number. This tells us that even if $\top$ and $\bot$ are distinct, they still each contribute the same number of elements (namely, 1) to the list. We can specify this "blindness" with the equality $z = \bot = \top$, so that

$$
L_2(z) = L_2(z, z) = \frac{1}{1 - 2z} = 1 + z + z + z^2 + z^2 + z^2 + z^2 + z^3 + z^3 + \dots
$$

simplifying, this series yields

$$
L_2(z) = 1 + 2z + 4z^2 + 8z^3 + \dots + 2^k z^k + \dots
$$

Since each of the lists under $z^3$ are lists of length 3, this series then tells us that there are $2^3$ distinct boolean lists of length 3.

Herein lies the power of these generating functions. By "erasing" properties that you don't care about (like the distinctness of true and false in a counting problem), you end up with this formal series whose coefficient gives the total count of a subclass of interest. Therefore, the question du jour of these "analytic" enumeration problems is not how one interprets giving $z$ a specific value, but rather how one can show that the function is analytic/differentiable around the origin and what its coefficients are.

This glosses over a lot of the details, but the intuition should hopefully remain. For your particular problem, we can follow the same recipe to eventually derive Knuth's tower of balanced tree construction.

Now, a height-balanced tree is a binary tree such that the height of each child of a tree is always within one unit of any other child of a tree. This gives a simple case-analysis to consider.

A balanced tree of height $h$ is a root node together with children such that they are:

• Balanced, so that the height of both children are the same, aka $h - 1$.

• Unbalanced but left-skewed, so that the height of the left children is larger, aka $h - 1$ and $h - 2$.

• Unbalanced but right-skewed, so that the height of the right children is larger, aka $h - 2$ and $h - 1$.

This then yields an inductive specification

$$
BBT_h = (BBT_{h-1}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-2}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-1}, \circ, BBT_{h-2})
$$

Where the tuple $(L, \circ, R)$ denotes the balanced tree rooted at $\circ$

StackExchange Computer Science Q#65452, answer score: 5