## n-ary Tree

 Question 1

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?

 A 3 B 4 C 5 D 6
Data Structures        n-ary Tree       Gate-2007
Question 1 Explanation:
L = (n-1) * I + 1
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n-1) * 10 + 1
40 = (n-1) * 10
n = 5
 Question 2
A complete n-ary tree is one in which every node has 0 or n sons. 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)
Data Structures        n-ary Tree       Gate-1998
Question 2 Explanation:
No. of internal node = x
Let no. of leaf nodes = L
Let nt be total no. of nodes.
So, L+x = nt -----(I)
Also for n-ary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = nt -----(II)
So, equating (I) & (II),
L+x = nx+1
L = x(n-1) + 1
There are 2 questions to complete.