2k views

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 | 2k views
0

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.

edited by
+1
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.

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

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

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

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)$.
Ans is A
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