NIELIT 2017 July Scientist B (CS) - Section B: 54

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 nodes is

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

Answer 1

every internal node is $k$ children

Total node$ =nk+1$(1 is for root)

$leaves$ =$total$ $node$ - $internal $ $node$

            $ =nk+1-n$

            $ =n(k-1)+1$

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

https://gateoverflow.in/1372/gate2005-36

https://gateoverflow.in//1683/gate1998-2-11#viewbutton

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