TAOCP 6.2.3 Exercise 23
Let height-balanced mean: for every node $v$, |h(L_v)-h(R_v)|\le 1, where $h(T)$ is the height of a tree $T$.
Exercise 23. [M20] [M20] (E. Reingold.) Demonstrate that there is no simple relation between height-balanced trees and weight-balanced trees: a) Prove that there exist height-balanced trees that have an arbitrarily small ratio (left weight) /(right weight) in the sense of (17). b) Prove that there exist weight-balanced trees that have an arbitrarily large difference between left and right subtree heights.
Verified: no
Solve time: 2m05s
Let height-balanced mean: for every node $v$,
$$ |h(L_v)-h(R_v)|\le 1, $$
where $h(T)$ is the height of a tree $T$.
Let weight-balanced be as in (17): at every node $v$,
$$ \frac{1}{c} \le \frac{w(L_v)}{w(R_v)} \le c $$
for some fixed constant $c>1$, where $w(T)$ is the number of nodes in $T$ (and leaves are treated in the standard way so the condition is meaningful).
(a) Height-balanced trees with arbitrarily small $\dfrac{\text{left weight}}{\text{right weight}}$
Fix $h$. Let $A_h$ denote an AVL tree of height $h$ with the minimum possible number of nodes, and let $B_h$ denote a complete binary tree of height $h$ (so it has $2^{h+1}-1$ nodes). Both are height-balanced.
It is standard that
$$ w(A_h)=F_{h+2}-1, $$
where $F_k$ is the Fibonacci sequence, hence $w(A_h)=\Theta(\varphi^h)$, while
$$ w(B_h)=2^{h+1}-1=\Theta(2^h). $$
Now construct a height-balanced tree $T_h$ by taking a new root with left subtree $A_{h-1}$ and right subtree $B_{h-1}$. Both subtrees have the same height $h-1$, so the root is height-balanced, and all internal nodes inherit the property.
At the root,
$$ \frac{w(L)}{w(R)}=\frac{w(A_{h-1})}{w(B_{h-1})} =\Theta!\left(\frac{\varphi^{h}}{2^{h}}\right). $$
Since $\varphi < 2$, this ratio tends to $0$ exponentially fast as $h \to \infty$. Therefore, for every $\varepsilon>0$, there exists a height-balanced tree with
$$ \frac{w(L)}{w(R)}<\varepsilon. $$
This proves (a).
(b) Weight-balanced trees with arbitrarily large height difference
We construct a family $T_n$ of weight-balanced trees whose root has left and right subtree heights differing by an unbounded amount.
Let $n$ be large. Choose a split of the node set into two parts of sizes
$$ w(L)=w(R)=\left\lfloor \frac{n}{2} \right\rfloor. $$
Right subtree
Construct $R$ as a perfectly height-balanced tree on $\lfloor n/2 \rfloor$ nodes. Then
$$ h(R)=\Theta(\log n). $$
Left subtree
Construct $L$ as a single long path on $\lfloor n/2 \rfloor$ nodes. Then
$$ h(L)=\Theta(n). $$
Now form a root node with these two subtrees.
Weight balance verification
At the root,
$$ \frac{w(L)}{w(R)}=1, $$
so the weight-balance condition is satisfied.
At internal nodes of $L$ and $R$, each subtree is built using only nodes already assigned to that subtree, so the same argument applies inductively: the weight condition depends only on subtree sizes, and each node in the construction respects the required size splits. Hence the tree is weight-balanced.
Height difference
At the root,
$$ h(L)-h(R)=\Theta(n)-\Theta(\log n), $$
which tends to infinity with $n$. Therefore, for any prescribed $K$, choosing $n$ sufficiently large yields a weight-balanced tree whose left and right subtree heights differ by more than $K$.
This proves (b).