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

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.

$$|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.

$$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$$.

• Damn, you beat me! May 11 at 21:07

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)$$.