Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in…
2015
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.
Attempted by 179 students.
Show answer & explanation
Correct answer: 199
Key insight: in any tree the number of edges equals the number of nodes minus one, which leads to a simple relation between leaves and nodes with two children.
Let n0, n1, n2 be the counts of nodes with 0, 1, and 2 children respectively.
Total nodes N = n0 + n1 + n2. Total edges (number of child links) = n1 + 2n2.
For any tree, edges = N - 1, so n1 + 2n2 = n0 + n1 + n2 - 1.
Cancel n1 from both sides and simplify to get n2 = n0 - 1.
Given n0 = 200 leaves, n2 = 200 - 1 = 199.
Therefore, the number of nodes that have exactly two children is 199.