edited by
22,964 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

Best answer
21 votes
21 votes

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 )

edited by
27 votes
27 votes
total nodes=nk+1(1 for root)

leaves =total nodes -internal nodes

            =nk+1-n

            =n(k-1)+1
2 votes
2 votes
#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
Answer:

Related questions

31 votes
31 votes
4 answers
1
Kathleen asked Sep 22, 2014
24,238 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,929 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,322 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