In a ternary tree, the number of internal nodes of degree 1,2, and 3 is 4,3,…
2018
In a ternary tree, the number of internal nodes of degree 1,2, and 3 is 4,3, and 3 respectively. The number of leaf nodes in the ternary tree is
- A.
9
- B.
10
- C.
11
- D.
12
Attempted by 116 students.
Show answer & explanation
Correct answer: B
Key idea: in a rooted tree the total number of child links equals the sum of degrees of internal nodes, and also equals total nodes minus 1.
Compute total child links from internal nodes: 1×4 + 2×3 + 3×3 = 19.
Count internal nodes: 4 + 3 + 3 = 10.
Let the number of leaves be L. Total nodes = internal + leaves = 10 + L, so total child links = (10 + L) − 1.
Set the two expressions for child links equal: 10 + L − 1 = 19. Solve to get L = 10.
Answer: 10 (the tree has 10 leaf nodes).
A video solution is available for this question — log in and enroll to watch it.