Min and max height of a binary tree

Question

Suppose I have n nodes, how can I find the max and min height of a tree?

I've seen varying statements for the min height such as $log_2 (n)$ and $log_2 (n+1)$ but I wasn't sure which was correct and I am unsure how to find the maximum height

Answer 1

If the tree is of maximum height: the tree is a list, and the height is $n$.

If the tree is of minimal height: let $h$ the height. The tree is full, hence at the height $2$ there are two nodes, and if there are $k$ nodes at one level then there are at most $2k$ nodes at the next level ($<2k$ only possible at the last level). From this you conclude that the nuumber os elements in an inner level $L$ is $2^{L-1}$ and

$$ \sum_{L= 1}^{h-1} 2^{L- 1} < n \le \sum_{L= 1}^h 2^{L- 1}\\ 2^{h- 1} < n \le 2^h $$

hence $h = 1 +E\left(\frac{ \log n}{\log 2}\right)$