title: Best case height for a binary tree with N internal nodes
body: <p>I am working through Algorithms in C++ by Robert Sedgewick and came across the following statement:</p>
  
  <blockquote>
    <p>The height of a binary tree with <code>N</code> internal nodes is at least <code>lg N</code>
    and at most <code>N-1</code>. The best case occurs in a balanced tree with <code>2^i</code>
    internal nodes at every level except possibly the bottom level. If the
    height is "h" then we must have</p>
  
  <pre><code>         2^(h-1) &lt; N+1 &lt;= 2^h
  </code></pre>
    
    <p>since there are N+1 external nodes.</p>
  </blockquote>
  
  <p>There wasn't much explanation surrounding the inequality, so my question is: how did the author deduce the inequality and what is it showing exactly?</p>
  
  <p>Thanks!</p>