# Do height-balanced binary trees have logarithmic depth?

A family of binary trees is called balanced if for every tree $$t$$ in the family the height of $$t$$ is $$O( \log n)$$.

Given a family of trees such that for every tree $$t$$ in the family, for every node $$v$$ in $$t$$, the height difference between the right subtree of $$v$$ and the left subtree of $$v$$ is at most $$c$$, where $$c$$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

• What is the claim you're trying to prove? Do you want to show that such a family is height balanced? – Steven Jun 4 '19 at 13:32
• Yes Steven. Exactly. We need to prove that this family is height balanced. – Neo182 Jun 4 '19 at 13:33
• Is this an infinite family? Big-O notation applies to asymptotic behavior, which doesn't apply to finite cases. – Acccumulation Jun 4 '19 at 21:40

Let us denote by $$N_h$$ the minimum number of leaves of a tree in your family of height $$h$$. Clearly $$N_0 = 1$$, and $$N_h = N_{h-1} + \min_{0 \leq d \leq c} N_{h-1-d}.$$ (Here $$N_h = 0$$ if $$h < 0$$.) You can prove inductively that $$N_h$$ is monotone, and so for $$h \geq c+1$$, $$N_h = N_{h-1} + N_{h-1-c}.$$ This is a recurrence relation whose solution is $$N_h = \Theta(\alpha^h)$$, where $$\alpha$$ is the maximal real root of $$x^{c+1} - x^c - 1= 0$$; for example, when $$c = 1$$, $$x$$ is the golden ratio.

Since the number of leaves in a tree of height $$h$$ is $$\Omega(\alpha^h)$$, it follows that a tree containing $$n$$ leaves has height $$O(\log n)$$.

• Hey Yuval. Thank you. I have few questions: 1. Why we want to show that Nh is monotone? And to show that I need to prove that Nh+1 >= Nh? 2. How do I reach the expression a^h? – Neo182 Jun 4 '19 at 16:06
• We want to show that $N_h$ is monotone so we could get a simpler recurrence relation for it. We can then solve it using classical techniques to get the answer $\Theta(\alpha^h)$. See for example Wikipedia. – Yuval Filmus Jun 4 '19 at 16:18

Let $$T_h$$ be any tree that satisfies your property and has height at least $$h$$. Let $$|T_h|$$ be the number of its nodes.

For $$0 \le h \le c$$, $$|T_h| \ge 1$$. For $$h > c \cdot i$$, with $$i \in \mathbb{N}^+$$, you have: $$|T_h| \ge 1 + | T_{c \cdot i} | + | T_{ c \cdot (i-1)}| \ge 2 | T'_{ c \cdot (i-1)}|,$$ where $$T_{c \cdot i}$$, $$T_{ c \cdot (i-1)}$$, and $$T'_{ c \cdot (i-1)}$$ are trees of height at least $$c \cdot i$$, $$c \cdot (i-1)$$, and $$c \cdot (i-1)$$, respectively, that also satisfy your property.

Let $$T$$ be a tree of height $$H$$ from your family. From the above observations (choosing $$h=H$$) it follows that $$|T| \ge 2^{\left\lfloor \frac{H}{c+1} \right\rfloor} \ge 2^{\frac{H}{c+1} - 1}$$, or equivalently, $$H \le (c+1)( 1+ \log |T|) = O(\log |T|)$$.

Thanks everyone for the answers. Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c. Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof. Instead of N(h) = N (h-1) + N (h-2) + 1 I used N(h) = N ( h -1) + N ( h - 1 - c) + 1