Height of epsilon-balanced binary search tree

Question

In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:

For example, one can say, a BST is balanced, if each subtree has at most epsilon * n nodes, where epsilon < 1 (for example epsilon = 3/4 or even epsilon = 0.999 -- which are practically not balanced at all). The reason for that is that the height of such a BST is roughly log_{1/epsilon}

I am a bit puzzled on the last statement -- how do we know that the height is roughly 1/epsilon?

Answer 1

Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has length $\ell$ (edges), then the last node contains at most $\epsilon^\ell n$ nodes, and so $\epsilon^\ell n \geq 1$, or equivalently, $\ell \leq \log_{1/\epsilon} n$.

• pete: shouldn't $\epsilon^\ell n \geq 1$ be a $\leq$ sign?
• Yuval Filmus: I think the inequality is in the correct direction.