A complete n-ary tree is one in which every node has either 0 or n children.…
1998
A complete n-ary tree is one in which every node has either 0 or n children. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by
- A.
x(n - 1) + 1
- B.
xn - 1
- C.
xn + 1
- D.
x(n + 1)
Attempted by 44 students.
Show answer & explanation
Correct answer: A
In a complete n-ary tree, every internal node has exactly n children. Let L be the number of leaves. Counting edges by parents gives nx edges, because each of the x internal nodes has n children. Counting edges by total nodes gives (x + L) - 1, because a tree with x + L nodes has one fewer edge than nodes. Equating both counts, nx = x + L - 1. Therefore, L = nx - x + 1 = x(n - 1) + 1. Hence, option A is correct.