An α-good tree with n nodes has height O(log n)

Question

Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by $|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We say that $T$ is $α$-good if, for every node $x$ in the tree with children $y$ and $z$, it holds that $|y|$ − $|z|$ ≤ $α|x|$. Show that an $α$-good tree with n nodes has height $O(\log n)$.

I tried using induction for this but made no progress.

Some other observations I made:

$|x| = |y| + |z| + 1$
$\le 2|z| - (|z| - |y|) + 1 $ (WLOG assume $|y|\le|z|$)
$\le 2|z| - ||z| - |y||+1$
$\le 2|z| - \alpha |x| + 1$
$ = 2|z| - \alpha |y| - \alpha |z| + (1 - \alpha)$

I'm not sure if it helps.

Answer 1

$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$ So, $|x| \ge \frac2{1+\alpha}|y|$.

Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)^k$.

If an $α$-good tree with $n$ nodes has height $h$, then $$n\ge \left(\frac2{1+\alpha}\right)^h$$

That is, $h\le\log_{\frac2{1+\alpha}}n$, which means $h=O(\log n)$ since $\frac2{1+\alpha}\gt1$.

Answer 2

First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| <\frac{1+\alpha}2 |x|$.

Now consider $h_n$ the maximal height of an $\alpha$-good tree of size $\leqslant n$. It is clear that $h_1 = 0$ (or $1$, depending on your definition of height). The property above shows that for $n\geqslant 2$, $h_n \leqslant 1 + h_{\left\lfloor\frac{1+\alpha}2n\right\rfloor}$.

An induction can now show that $h_n \leqslant \log_{\beta}(n)$, with $\beta = \frac2{1+\alpha}$. Since $\alpha < 1$, this is clearly in $\mathcal{O}(\log n)$.