[Math] the minimum height of a binary tree with $n$ vertices

Question

What is the minimum height of a binary tree with $n$ vertices?

Is it $$\lceil \log_2n\rceil$$,

$$\lfloor \log_2{n} \rfloor$$

or

$$\lceil \log_2{n+1} \rceil -1$$

Answer 1

So we can see that if we let $n$ and $x$ be a natural number then,

Height 0 - $2^0$

Height 1 - $2$ $\le$ n $\le $$3$

Height 2 - $4$ $\le$ n $\le $$7$

Height 3 - $8$ $\le$ n $\le $$15$

Height 4 - $16$ $\le$ n $\le $$31$

Using mathematical deduction we can conclude,

Height x - $2^x$ $\le$ n $\le $$2^{x+1}-1$

And since we want the least number of terms for the minimum height of the graph we take into consideration the term on the left of the inequality. Further, in order to get the term of the least number of vertices of a given height n must equal to $2^x$ and so,

$n=$ $2^x$ $\Longrightarrow$ $\log_2{n}$ $=x$

Therefore in order to get the least number in each interval we can conclude,

$\lfloor \log_2{n} \rfloor$ $=$ $x$