In a complete k-ary tree, every internal node has exactly k children. The…
2005
In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
- A.
nk
- B.
(n - 1)k + 1
- C.
n(k - 1) + 1
- D.
n(k - 1)
Attempted by 187 students.
Show answer & explanation
Correct answer: C
Key insight: count the child links (edges) in two different ways.
Each internal node has k children, so the total number of child links is k × n.
Every node except the root is a child of exactly one internal node, so the total number of child links is total nodes − 1 = n + L − 1, where L is the number of leaves.
Equate the two expressions and solve for L:
k n = n + L − 1 ⇒ L = k n − n + 1 = n(k − 1) + 1.
Therefore the number of leaves is n(k − 1) + 1.