A 5-ary tree is tree in which every internal node has exactly 5 children. The…
2018
A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left (Leaf) nodes in such a tree with 8 internal nodes will be :
- A.
30
- B.
33
- C.
45
- D.
125
Attempted by 170 students.
Show answer & explanation
Correct answer: B
Key idea: For a full m-ary tree (every internal node has exactly m children), the number of leaves L and internal nodes I satisfy a simple relation.
Each internal node has m children, so the total number of edges in the tree is m × I.
If N is the total number of nodes, edges = N − 1, hence N − 1 = mI, so N = mI + 1.
But N = I + L, so I + L = mI + 1. Rearranging gives L = (m − 1)I + 1.
Apply to this problem: m = 5 and I = 8, so L = (5 − 1)×8 + 1 = 4×8 + 1 = 33.
Answer: 33 leaf nodes.
A video solution is available for this question — log in and enroll to watch it.