The minimum height of a binary tree of n nodes is ______.
A)n
B)n / 2
C)(n / 2)- 2
D)log2(n + 1)

Question

Quizplus · Accepted Answer

The minimum height of a binary tree with n nodes is achieved when each level of the tree is completely filled, except possibly the lowest level, which is filled from left to right. In other words, if the height of the tree is h, then there are at least 2^h−1 nodes in the tree (since the maximum number of nodes in a binary tree of height h is 2^h-1). Solving for h in terms of n, we have:
n≥(2^h−1) 
n+1≥2^h 
log2(n+1)≥h 
Therefore, the minimum possible value of h (i.e., the minimum height of a binary tree of n nodes) is log2(n+1).

The Minimum Height of a Binary Tree of N Nodes