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

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

---

First thing that comes in mind is that it is a complete tree and total nodes are 10+41=51
so assume any 'n' from options like n=5 and keep adding nodes of each level till the 2nd last level
5^0 + 5^1 + 5^2 now if you will add 5^3 then it will exceed total number of nodes (i.e. 51)
remaining nodes in last level = 51-(1+5+25) = 20

 

now here we know that every nodes has either 0 children or 'n' children so the remaining nodes in the last level should be divisible by 'n' and yes 20 is divisble by 5
This won't satisy other options, it will hardly take 40-50 seconds to solve for all the options

Thus option C is correct (let me know if I missed something)

---

similar questions for practice

Data Structures: GATE CSE 2005 | Question: 36

Data Structures: GATE CSE 1998 | Question: 2.11

Data Structures: GATE CSE 2002 | Question: 2.9

Answer 1

If you do little bit experiments on no of leaves, Internal nodes, you will realize that they have equation like following :-

No of leaves $(L) = (n-1) *$ Internal Nodes $(I) + 1$

Here we need to find $n$.

Putting values

$41 = (n-1) * 10 + 1$
$\implies(n-1) * 10 = 40$
$\implies n-1 = 4$
$\implies n = 5$

So, answer is C.

Comments

total no. of nodes (t) = L(leaf node) + I (internal node)

t = 41 + 10

t= 51

edges (e) = t – 1

0* L + n*I = 51 -1

n*10 = 50

n = 5

---

Good question.

---

since,L=41 and I=10 we know that

Total nodes=L+I=41+10=51

Total nodes =I*K+1

51=10*k+1

k=5.

so each internal node has 5 child

Answer 2

Sum of degrees in tree $= L +  I \times (n+1) - 1 = 10n + 50 ($Each leaf node has degree 1 and all internal nodes have degree $k+1,$ except root which has degree $k)$

So, number of edges $= 5n + 25 ($Number of edges in a graph (hence applicable for tree also) is half the sum of degrees as each edge contribute $2$ to the sum of degrees)

In a tree with $n$ nodes we have $n-1$ edges, so with $41+10 = 51$ nodes, there must be $50$ edges.

So, $5n + 25 = 50$

$\implies 5n = 25$

$\implies n = 5$

Comments

great..

---

@arjun sir in this https://gateoverflow.in/3548/gate2006-it-9 u told that tree can be considered as directed graph and only outgoing edge can be considered as degree and leaf has a 0 degree then sum of degree = no of edges .In this why different 

---

@once_2019 i think this solution is question specific.

In tree degree of node means it's outgoing edges. right ?

Answer 3

Full m-ary tree means : Every internal node have exactly m children. Other way, each node has zero or m children only. 

Some of the full m-ary trees.

T1 (m=2) ,  T2 (m=3) , T3 (m=5)  are full but T₄ is not.

In this question, how they define complete means the full m-ary tree. We have n-ary tree and Internal nodes ( I ) = 10 , Leaf nodes ( L ) = 41

$n = L+ I \\ =>n = 51 \\ =>n*10+1 = 51 \\ =>n = 5$

Comments

same way.. i have done

---

reference?..............rosen?????

---

Nice way to approach. Learned a new approach today :). Thanks

---

took an example of 3-ary  tree then got the answer

Answer 4

Total number of internal nodes = $I=10$
Total number of leaf nodes = $L=41$

for a $n-ary$ tree, levels starts with $0$ and at each level there are $n^k$ nodes; where $k$ it the level number.

\[\begin{align*} \text{total number of nodes} - L &= I \\ \left( 1 + n^1 + n^2 + \dots + n^k \right) - L &= I \\ \left( 1 + n^1 + n^2 + \dots + n^k \right) - 41 &= 10 \\ \left(n^1 + n^2 + \dots + n^k \right) &= 50 \\ \frac{n(n^k-1)}{n-1} &= 50 \qquad \text{;on putting }n=5 \\ n^k &= 41\\ \end{align*}\]

where, $n^k$ represents number of nodes in last level i.e. leaf nodes, so on taking option C verifies it.

Hence, answer = option C

Answer 5

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

---

Good approach

Answer 6

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