A binary tree T has 20 leaves. The number of nodes in T having two children is…
2015
A binary tree T has 20 leaves. The number of nodes in T having two children is _______.
Attempted by 76 students.
Show answer & explanation
Correct answer: 19
Answer: 19
Explanation:
Let n0 be the number of leaves, n1 the number of nodes with one child, and n2 the number of nodes with two children.
Total nodes N = n0 + n1 + n2. A tree with N nodes has N - 1 edges. Also counting child links gives edges = n1 + 2·n2.
Equate the two expressions for edges: n1 + 2·n2 = n0 + n1 + n2 - 1, which simplifies to n2 = n0 - 1.
Given n0 = 20 leaves, n2 = 20 - 1 = 19.
A video solution is available for this question — log in and enroll to watch it.