GATE CSE 2007 | Question: 43

Question

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$

Comments

if 1-ary tree and 'i' is internal node then no of leave is 1

if 2-ary tree and 'i' is internal node then no of leaves are (i+1)

if 3-ary tree and 'i' is internal node then no of leaves are (2i+1)

if 4-ary tree and 'i' is internal node then no of leaves are (3i+1)

if n-ary tree and 'i' is internal node then no of leaves are (n-1)i+1

given that leaves L=41,internal node i=10,,

then L=(n-1)i+1

41=10n-10+1

10n=50

n=5

---

use two-equation 

N=L+i  ...(1)

N=M(i)+1... (2)

where n= total node in M-ary tree 

i= internal node 

 

---

No.of leaves (L)= (N-1)*INTERNAL NODE(I)+1

we find value of n.

41= (n-1)*10+1

= (n-1)*10=40

= n-1=4

n=5

 

SO answer will be option c

Answer 1

for this type of question, don't remember formulas simply learn derivations

total number of nodes (N) = internal nodes (n)+ leaf nodes(L)

total  number of edge(E)= N-1

so here internal node=10 , leaf nodes=41

so edge(E)= 10+41-1=50

again Edge E= maximum child size of internal nodes* total internal nodes

so, 50= I*10

I=5

Comments

Total node = internal node + leaf node

Total node = (no. Of child node) *internal_node + 1

Both equation are equal..
So, n*10+1=10+41

n=5

Answer 2

most of the solutions have used some equation, so I tried with the basic handshaking lemma. Do point out it you find anything incorrect

Answer 3

We could prove it with graph theory too. Notice from the following figure that there are only 3 types of nodes in a complete n-ary tree with N = I + L nodes, i.e., with I internal and L leaf nodes:

1. 1 root node, with degree exactly n
2. (I-1) internal nodes, each with degree exactly n+1 (since root is also an internal node)
3. L leaf nodes, each with degree 1

 

Now, if we use the following two facts from graph theory:

5. A tree with N nodes has N-1 edges
6. Sum of the degrees of nodes in any graph is twice the number of edges in the graph

Combining all the above, we get,

Sum of degrees of all the nodes in the tree

= 1.n + (I-1)(n+1) + L.1 = 2(I+L-1)

=> L = (n-1)I + 1​

=>  n = (L - 1) / I + 1 = 40/10 + 1 = 5

Answer 4

Consider this simple binary tree
it has got L=4 I=3
Leaves have got a degree of 1, internal nodes have a degree of 3(excluding root), and root has got a degree of 2.
ie, 1*L+ (3)(I-1)+2(1)=2(E)
 or 2*E=4+6+2
or E=6

Now we could generalize this formula for n-ary tree as
1*L+(n+1)(I-1)+n=2(E)
=> where E again is (total number of nodes -1), over here is 51-1=50,
1*L + (n+1)(I-1)+n=100
=>1*41+(n+1)(10-1)+n=100
=>41+9n+9+n=100
=>n=5