# Height of epsilon-balanced binary search tree

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?

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$$.
• shouldn't $\epsilon^\ell n \geq 1$ be a $\leq$ sign? – pete Oct 6 '19 at 1:43