TAOCP 6.2.3 Exercise 6
Let $B_h(z)$ denote the ordinary generating function in which the coefficient of $z^n$ equals the number of balanced binary trees with $n$ internal nodes and height exactly $h$.
Exercise 6. [M21] [M21] Prove that Eq. (5) defines the generating function for balanced trees of height h.
Verified: yes
Solve time: 58s
Solution
Let $B_h(z)$ denote the ordinary generating function in which the coefficient of $z^n$ equals the number of balanced binary trees with $n$ internal nodes and height exactly $h$.
A balanced tree of height $h$ consists of a root node and two ordered subtrees. The root contributes one internal node, giving a factor $z$. If the left and right subtrees have generating functions $F(z)$ and $G(z)$, then the corresponding class contributes $zF(z)G(z)$ by the product rule for ordered pairs.
In a balanced tree of height $h$, each subtree height is constrained by the definition of balance. If the whole tree has height $h$, then at least one subtree has height $h-1$, and the other has height either $h-1$ or $h-2$. No other height combinations occur, since a subtree of height $\le h-3$ would force the total height to be at most $h-1$.
Thus the admissible ordered pairs of subtree heights are
$$ (h-1, h-1), \quad (h-1, h-2), \quad (h-2, h-1). $$
These cases are disjoint, since the height pair uniquely determines the structure class of the root decomposition. The corresponding combinatorial specification is therefore
$$ \mathcal{B}h = \mathcal{Z} \times \left( \mathcal{B}{h-1}\times \mathcal{B}{h-1} ;\cup; \mathcal{B}{h-1}\times \mathcal{B}{h-2} ;\cup; \mathcal{B}{h-2}\times \mathcal{B}_{h-1} \right), $$
where $\mathcal{Z}$ denotes a single node.
Translating this specification into generating functions uses the rules that disjoint union becomes addition and ordered product becomes multiplication. The factor $\mathcal{Z}$ contributes $z$. Hence
$$ B_h(z) = z\left(B_{h-1}(z)B_{h-1}(z) + B_{h-1}(z)B_{h-2}(z) + B_{h-2}(z)B_{h-1}(z)\right). $$
Simplifying the middle terms yields
$$ B_h(z) = z\left(B_{h-1}(z)^2 + 2B_{h-1}(z)B_{h-2}(z)\right). $$
This is exactly Eq. (5), and every term corresponds bijectively to a unique balanced tree of height $h$ via decomposition at the root. This completes the proof. ∎