Data-Structures
November 15, 2023Question 8932 – Compiler-Design
November 15, 2023Data-Structures
|
Question 40
|
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
|
x(n-1) + 1
|
|
|
xn – 1
|
|
|
xn + 1
|
|
|
x(n+1)
|
Question 40 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
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
Correct Answer: A
Question 40 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
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