The number of leaf nodes in a rooted tree of n nodes, with each node having 0…
2002
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
- A.
n/2
- B.
(n - 1)/3
- C.
(n - 1)/2
- D.
(2n + 1)/3
Attempted by 34 students.
Show answer & explanation
Correct answer: D
Let I be the number of internal nodes and L be the number of leaf nodes. Since every internal node has exactly 3 children, the total number of edges is 3I. A rooted tree with n nodes has n - 1 edges, so 3I = n - 1 and I = (n - 1)/3. Also, n = I + L. Therefore, L = n - I = n - (n - 1)/3 = (2n + 1)/3.