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?


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

  • $\begingroup$ shouldn't $\epsilon^\ell n \geq 1$ be a $\leq$ sign? $\endgroup$ – pete Oct 6 '19 at 1:43
  • $\begingroup$ I think the inequality is in the correct direction. $\endgroup$ – Yuval Filmus Oct 6 '19 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.