A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, What is the value of n ?

The correct answer is option 3.

Key Points

If the tree is 1-ary and 'I' is an internal node, the number of leaves is 1
If the tree is 2-ary and  'I' is an internal node, the number of leaves is I+1
If the tree is 3-ary and 'I' is an internal node, the number of leaves is 2I+1
If the tree is 4-ary and  'I' is an internal node, the number of leaves is 3I+1
If the tree is 5-ary and 'I' is an internal node, the number of leaves is 4I+1
If the tree is n-ary and  'I' is an internal node, the number of leaves is (n-1)I+1
Given that leaves L= 41, internal nodes I=10
L=(n-1)I+1
41=10(n-1)+1
10n=50
n=5 

∴ Hence the correct answer is 5.

Internal nodes  I=10
Leaf nodes  L=41

In an n-ary tree, the levels start at 0 and there are n^k nodes at each level, where k is the level number.

Total number of nodes−L=I

(1+n¹+n²+⋯+n^K)−L=I

(1+n¹+n²+⋯+n^K)−41=10

(n¹+n²+⋯+n^K)=50

 $\frac{n(n^K-1)}{n-1}$=50

Option verify, if n=3, nK=35 is not equal to leaves.

if n=4, nK=39 is not equal to leaves.

if n=5, nK=41 is equal to leaves. So, it is 5-ary tree.

if n=6, nK=43 is not equal to leaves.