GATE CSE 1998 | Question: 2.11

Question

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

• A. $x(n-1) +1$
• B. $xn-1$
• C. $xn +1$
• D. $x(n+1)$

Comments

Similar question :

https://gateoverflow.in/1372

---

Draw a full BT and eliminate the options

---

Another way to solve:
Total no of nodes = ( No of internal nodes * k ) + 1
Internal Nodes + Leaf nodes = ( No of internal nodes * k ) + 1
where,
k = Internal node contributes k children

Given:
Internal nodes = x
Leaf nodes = L
K = n           

x + L = xn + 1
L = xn + 1 - x
L = x(n-1) + 1
option a)
 

Answer 1

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 add $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$ new nodes & 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.

Comments

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.

---

Total no. of nodes = Internal nodes + leaf nodes

 N = x + l

edges = N-1

0 * l  + n * x = x + l -1

l = x ( n – 1 ) +1

---

Kiyoshi That is applicable in Binary tree with internal nodes of degree 2 is one less than the total leaves in that tree but its not apllicable here

---

First we have $1$(leaf) node.

We add $n$ leaves to it, but in the process we loose $1$ leaf because the parent of these leaves becomes a internal node.

So total leaves $=\underbrace{1}_\text{previous leaf}+(\underbrace{n}_\text{adding n child}-\underbrace{1}_\text{making the parent internal node})$

Now lets say we decide to add leaf node to $k$ different nodes(which are leaves obiously). In the process of doing it we add $kn$ leaves but also loose $k$ leaves (these will become internal nodes).

Now total leaves $=1+(n-1)+k(n-1)=(k+1)(n-1)+1$

Now can you guess what is the term $(k+1)$ ?

Yes indeed it is the total number of internal nodes where $k$ is the new internal nodes and $1$ was previous internal node.

Answer 2

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

Answer 3

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

Answer 4

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 5

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

Answer 6

Recursive solution for this problem:

$T(x) = T(x-1) + n -1$

$T(0) = 1$

---

$T(x) = T(x-i) + i \cdot (n-1) $

when i=x, we have x-i = 0

$T(x) = T(0) + x\cdot(n-1)$

$ = 1 + x\cdot (n-1)$

Hence option A

Comments

$T(x)=$ Number of Leafs when there is $x$ Internal Nodes