# GATE2005-36

4.8k views

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:

1. $nk$
2. $(n-1)k + 1$
3. $n(k-1) +1$
4. $n(k-1)$
in DS
edited
0

Before looking at answer just  form following two equation and try to solve -->

1. Equation for total degree.
2. Equation for total node.
0
0
sum of degree$:l+(n-1)(k+1)+k=2e$

sum of degree$:l+kn+n-1=2e$

# of edges e$=\dfrac{l+kn+n-1}{2}$

and also # of edges in a tree $=(l+n)-1$

$\therefore \dfrac{l+kn+n-1}{2}=l+n-1$

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

Answer :-> C) $n(k-1) +1$

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 )

edited by
0
Thanks for your explanation sir :-)
total nodes=nk+1(1 for root)

leaves =total nodes -internal nodes

=nk+1-n

=n(k-1)+1
1
here k is not internal node ..... n is internal node and

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
0

It was typo thanks for correcting...

0

@Pooja Palod

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

0

@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 !

Option c.

 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
#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
0
@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
0
in some que root node is not consider as internal node but in thi que root node is consider as internal node..why ??
1 vote

To answer this type of question while practicing, always prefer derivation method instead of hit and trial

let total number of nodes =N

so N= total number of leaves nodes(say L) +total number  no internal nodes (n )

edge (E)= N-1  => E= n + L -1                     ............(1)

again edge (E)= (n* k) + (L*0)               ............(2) //{because only internal nodes are involved in forming an edge}

so from equation 1 and 2

n + L -1 = n*k

L=nk - n + 1

L=n(k-1)+ 1

## Related questions

1
3.1k views
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is: $10, 8, 7, 5, 3, 2, 1$ $10, 8, 7, 2, 3, 1, 5$ $10, 8, 7, 1, 2, 3, 5$ $10, 8, 7, 3, 2, 1, 5$
Postorder traversal of a given binary search tree, $T$ produces the following sequence of keys $10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29$ Which one of the following sequences of keys can be the result of an in-order traversal of the tree $T$? $9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95$ ... $29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95$ $95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29$