The Gateway to Computer Science Excellence

+23 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

- $x(n-1) +1$
- $xn-1$
- $xn +1$
- $x(n+1)$

+32 votes

Best answer

Answer : $\rightarrow$ (**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.

+2

let d be the no of leaves in this complete n ary tree.

Now, total no of degrees of a n ary tree is = 1*n+(x-1)(n+1)+d*1

Now this is because for root there is 1 node and it has n children so degree n now here it is mentioned that there are x is the total no of internal nodes we know that internal nodes include root as well as all nodes excluding the leaves so we can get that (x-1) is the no of nodes of this type and they have each (n+1) degree and d is the no of leaf nodes they have degree 1 each.

So we get that the total no of degrees =

1*n+(x-1)*(n+1)+d*1

And the total no of nodes= d+(x-1)+1(for root)=d+x

Now the no of edges = ( n*1+(x-1)(n+1)+d) /2 (by formulae)........(1)

now no of edges for a tree is= total no of nodes -1

total nodes= 1+ d+(x-1)=x+d

so total edges= (x+d-1).............(2)

Now equating 1 and 2 we get,

d=(nx-x+1)

d= 1+(x)(n-1) option A.

Now, total no of degrees of a n ary tree is = 1*n+(x-1)(n+1)+d*1

Now this is because for root there is 1 node and it has n children so degree n now here it is mentioned that there are x is the total no of internal nodes we know that internal nodes include root as well as all nodes excluding the leaves so we can get that (x-1) is the no of nodes of this type and they have each (n+1) degree and d is the no of leaf nodes they have degree 1 each.

So we get that the total no of degrees =

1*n+(x-1)*(n+1)+d*1

And the total no of nodes= d+(x-1)+1(for root)=d+x

Now the no of edges = ( n*1+(x-1)(n+1)+d) /2 (by formulae)........(1)

now no of edges for a tree is= total no of nodes -1

total nodes= 1+ d+(x-1)=x+d

so total edges= (x+d-1).............(2)

Now equating 1 and 2 we get,

d=(nx-x+1)

d= 1+(x)(n-1) option A.

+15 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**

+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.)

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.)

+6 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

+5 votes

Each of the $x$ internal nodes has exactly $n$ edges connected to it. So there are $xn$ edges in the tree. Some of these edges have other internal nodes at the other end and some have leaves at the other end. Except for the root, all other internal nodes are at the other end of an edge starting at an internal node. Thus to get the number of leaves we compute the number of edges with leaves at the other end. We do this by subtracting $x-1$ from $xn$. Hence the formula is $xn - (x-1)$.

0 votes

A complete n-ary tree has x number of internal nodes. Each such internal nodes has n children, Now except root node every other node(may be leaf or internal) is a children of some other internal node, there are nx numbers of such nodes(x internal nodes, each having n children, so total nx), now if we add 1 (for root) to nx , which is nx +1 ,we will get total number of nodes in the tree.

Total number of nodes= nx +1 , number of external nodes= x , So, total leaves= nx+1-x = x(n-1) +1

Total number of nodes= nx +1 , number of external nodes= x , So, total leaves= nx+1-x = x(n-1) +1

52,315 questions

60,436 answers

201,777 comments

95,257 users