Consider a binary tree with n nodes, where each node can have at most two…
2009
Consider a binary tree with n nodes, where each node can have at most two children. The height of the tree is defined as the maximum number of edges between the root node and any leaf node. Which of the following statements is true regarding the height h of this binary tree?
- A.
The height of the tree is always equal to n-1.
- B.
The height of the tree can be greater than or equal to n-1.
- C.
The height of the tree is always equal to log₂(n).
- D.
The height of the tree can be greater than or equal to log₂(n).
Attempted by 402 students.
Show answer & explanation
Correct answer: D
For a binary tree with n nodes, the height h is bounded. The minimum height occurs in a complete binary tree and equals floor(log2(n)). The maximum height occurs in a skewed tree and equals n-1. Therefore, the height h satisfies floor(log2(n)) <= h <= n-1.