Of the following, which best approximates the ratio of the number of…
2020
Of the following, which best approximates the ratio of the number of non-terminal nodes in the total number of nodes in a complete K-ary tree of depth N ?
- A.
1/N
- B.
(N-1)/N
- C.
1/K
- D.
(K-1)/K
Attempted by 228 students.
Show answer & explanation
Correct answer: C
In a complete K-ary tree, the number of leaf nodes grows exponentially faster than internal nodes as depth increases. Specifically, for large N, the ratio of leaf nodes to total nodes approaches (K-1)/K. Since non-terminal nodes are the complement of leaf nodes in the total count, their ratio approaches 1 - (K-1)/K = 1/K.
A video solution is available for this question — log in and enroll to watch it.