What is the value for the number of nodes of rank r?

› Category: Questions › What is the value for the number of nodes of rank r?
0 Vote Up Vote Down
Editor">Editor Staff asked 1 month ago

What is the value for the number of nodes of rank r?
 
(a) N
 
(b) N/2
 
(c) N/2^r
 
(d) N^r
 
This intriguing question comes from Trees topic in portion Trees of Data Structures & Algorithms I
 
This question was addressed to me during an online exam.

Question Tags:
1 Answers
0 Vote Up Vote Down
Editor">Editor Staff answered 1 month ago

Correct choice is (c) N/2^r
 
For explanation: Each node of a rank r is the root of a subtree of at least 2^r. Therefore, there are at most N/2^r disjoint subtrees.