Height of epsilon-balanced binary search tree 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 &lt; 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$.