Binary Trees Quiz 2

Question :

In a complete k-ary tree, every internal node has exactly k children or no child. 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)

Solution :

C) is correct

For an k-ary tree where each node has k children or no children, following relation holds L = (k-1)*n + 1 Where L is the number of leaf nodes and n is the number of internal nodes. Let us see following for example
             o
           / | \
          o  o  o
        /|\    /|\
       o o o  o o o
               /|\
              o o o
k = 3
Number of internal nodes n = 4
Number of leaf nodes = (k-1)*n  + 1 = (3-1)*4 + 1 = 9

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.