edited by
14,544 views
29 votes
29 votes

A complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is given by

  1. $x(n-1) +1$
  2. $xn-1$
  3. $xn +1$
  4. $x(n+1)$
edited by

11 Answers

Best answer
41 votes
41 votes

Correct Option: A

$x(n-1) +1$

Originally when we have root , there is only $1$ node, which is leaf. (There is no internal node.) From this base case "+1" part of formula comes.

When we $n$ children to root, we make root internal. So then Total Leaves $= \ = 1(n-1) + 1 = n$.

In complete $n$ ary tree every time you add $n$ children to node, you add $n-1$ leaves & make that node to which you are inserting childen internal.( $+n$ for leaves, $-1$ for node which you are attaching ). So if you had originally few leaves, you add $n-1$ "New" leaves to them. This is how $x(n-1) +1$ makes sense.

edited by
20 votes
20 votes

As they said in question A complete n-ary tree is one in which every node has 0 or n sons.

lets take few case's and analyze them 

if we consider n = 2 (A Binary tree in place of n-ary tree See figure 1)

if we consider n = 3 (A 3-ary tree in place of n-ary tree See figure 2)

if we consider n = 4 (A 4-ary tree in place of n-ary tree See figure 3)

       

Type of Tree Internal Node (x) Leaf Nodes
Binary 3 4
3-ary 3 7
4-ary 3 10
5-ary 3 13

In Given Options put the values of internal nodes and type of tree and get the relation

    x(n-1)+1     xn-1     xn+1    x(n+1)
3(2-1)+1 = 4  3*2 - 1 = 5 3*2+1 = 7 3(2+1) = 9
6+1 = 7 8 10 12
10 11 13 15

Answer : Option A

edited by
7 votes
7 votes

let

i = # internal nodes

l = # leaves

n = total # nodes 

then for m-ary tree

total # nodes(n)  = m* i + 1.......................(1)   

also u know  total # nodes(n) = i + l............(2)

now u use these two formula

n x + 1 = x + l

so l = x * (n-1) + 1

6 votes
6 votes
if 1-ary tree and x is internal node then no of leave is 1

if 2-ary tree and x is internal node then no of leaves are (x+1)

if 3-ary tree and x is internal node then no of leaves are (2x+1)

if 4-ary tree and x is internal node then no of leaves are (3x+1)

if n-ary tree and x is internal node then no of leaves are (n-1)x+1

so ans is A.)
Answer:

Related questions

21 votes
21 votes
1 answer
2
Kathleen asked Sep 26, 2014
4,132 views
Derive a recurrence relation for the size of the smallest AVL tree with height $h$.What is the size of the smallest AVL tree with height $8$?
26 votes
26 votes
5 answers
3