edited by
22,987 views
22 votes
22 votes

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)$
edited by

8 Answers

1 votes
1 votes

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

0 votes
0 votes

# edges = # nodes – 1

#nodes = #edges + 1

$n _{0 } + n_{k} = n _{0 } * 0 + n _{k } * k + 1$,        where  $n
_{0
                                               }$   is  nodes with 0 child and $n
                                                     _{k
                                                         }$  is nodes with exactly k children

 $n _{0 }  = n _{k } * k + 1 – n _{k } $

$n _{0 }  = n _{k }( k-1) + 1  $

So, (C) is the correct option.

0 votes
0 votes
K=2 (BINARY TREE) SO,  NODE =7  N=3(INTERNAL NODE)  LEAF =4

A)-nk=3*2=6.

B)-(n-1)k+1=4+1=5

c)-k(n-1)+1=3+1=4.

d)-n(k-1)=3.

TAKE MIN HEIGHT =2.
0 votes
0 votes
we know that :- Total Nodes (N) =  Internal Nodes(I) + Leaf Nodes(L)

here we are given with :- I = n

so, N = n+L → (1)

we also, know that :-  In an k-ary tree the total number of edges are contributed by Internal nodes only and so, the relation between Internal nodes and the number of edges is given by, k * I = (N-1)

                                                                              => N = k*n + 1 → (2) , since, I=n(given)

so, from equations 1 and 2, we have,  n+L = k*n+1

=> L = k*n – n + 1

=> L = n(k-1)+1 is the answer.
Answer:

Related questions

31 votes
31 votes
4 answers
1
Kathleen asked Sep 22, 2014
24,261 views
How many distinct binary search trees can be created out of $4$ distinct keys?$5$$14$$24$$42$
20 votes
20 votes
1 answer
2
Kathleen asked Sep 22, 2014
13,945 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$ ar...
43 votes
43 votes
8 answers
3
Kathleen asked Sep 22, 2014
19,340 views
An Abstract Data Type (ADT) is:same as an abstract classa data type that cannot be instantiateda data type for which only the operations defined on it can be used, but no...
22 votes
22 votes
3 answers
4