GATE CSE 2005 | Question: 36

Question

In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is:

• A. $nk$
• B. $(n-1)k + 1$
• C. $n(k-1) +1$
• D. $n(k-1)$

Comments

total no. of nodes(t) = n + l (leaf node)

e = t – 1

0*l + k*n = n + l -1

l = n (k-1) + 1

---

Every internal node adds n leaves & subtracts 1 leave expect for the root.Root as an internal node directly add n leaves & a single node is just a 1 leaf.

---

For any $k$-ary tree:

1. $N=I+L$
2. $N=k*I+1$

from ! and 2:

$I+L=k*I+1$

$\implies n+L=k*n+1$

$\implies L=k*n-n+1$

$\implies L=n(k-1)+1$

Note:

• $N=$ total number of nodes
• $I=$ number of internal node
• $L=$ number of leaf node
• $k=k-$ary tree

Answer 1

Correct Option: C 
Originally when we have root , there is only $1$ node, which is leaf.(There is no internal node.) From that "$+1$" part of formula comes from this base case.

When we $k$ children to nodes, we make root internal. So then Total Leaves $= n(k-1) + 1 = (k-1) + 1 = k$

In $k$ complete $k \ ary$ tree every time you add $k$ children , you add $k-1$ leaves.( $+k$ for leaves, $-1$ for node which you are attaching )

Comments

Thanks for your explanation sir :-)

---

Similar question :

GATE CSE 1998 | Question: 2.11

Answer 2

total nodes=nk+1(1 for root)

leaves =total nodes -internal nodes

            =nk+1-n

            =n(k-1)+1

Comments

@Pooja Palod

I've one doubt... How do u get total number of nodes=nk+1?

---

@Pooja I couldn't get why you added 1 ? Is n't root is also an internal node ? So for n internal nodes having k children for each then it should be nk nodes in total ,why you adding 1 for root extra ,can you please explain ,thank you !

---

why root is not counted as internal node. 

@gatecse 

 

Answer 3

 

Comments

leaves node = internal node (k-1)+1

leaves= n(k-1)+1

and total nodes = n(k-1)+1+n= nk+1

so ans should be (c)

http://www.geeksforgeeks.org/g-fact-42/

https://gateoverflow.in//1683/gate1998_2-11#viewbutton

Answer 4

#leaves * degree_of_each_leave + #internal_nodes(excluding the root) *degree_of_each_internal node + degree of root=2(number of edges)

number of leaf node is( say l)

here degree of leaf node is 1

number o internal nodes(excluding root)is n-1

degree of each internal node is k+1

degree of root is k

number of edges=l+n-1

 

l+(n-1)(k+1)+k=2(l+n-1)

=>l+nk-k+n-1+k=2l+2n-2

=>l=n(k-1)+1

Comments

@Bhagi

more precisely just solve this two equation to get answer of any such ques!

N=ki+1

N=i+l

where  N=number of nodes i=no of internal node k= k-ary l=leaves

---

in some que root node is not consider as internal node but in thi que root node is consider as internal node..why ??