GATE CSE 2002 | Question: 2.9

Question

The number of leaf nodes in a rooted tree of n nodes, with each node having $0$ or $3$ children is:

• A. $\frac{n}{2}$
• B. $\frac{(n-1)}{3}$
• C. $\frac{(n-1)}{2}$
• D. $\frac{(2n+1)}{3}$

Comments

Solve the equation, took - 2L on rhs to lhs..

---

Let \( L \) = number of leaves, and \( I \) = number of internal nodes.

W.K.T. in a tree:

• The number of edges is \( n-1 \).  ⇒  Total edges = \( 3 *  I  \)
  
   
• Each internal node has 3 children, so contributes 3 edges.

We have:
\[
n = L + I
\]
Also,
\[
3I = n-1 \quad \Rightarrow \quad I = \frac{n-1}{3}
\]

Substituting:
\[
L = n - I = n - \frac{n-1}{3}
\]
\[
= \frac{3n - (n-1)}{3}
\]
\[
= \frac{2n+1}{3}
\]

Thus, the number of leaf nodes is:
\[
\boxed{\frac{2n+1}{3}}
\]

 

---

${take \ just \ 1\ node\ root\ w/o\ child}$

$\underline{option \ a}$: 1/2

$\underline{option \ b}$: 0/3 = 0

$\underline{option \ c}$: 0/2 =0

$\underline{option \ d}$: 3/3 = 1

$\therefore option \ d$

Answer 1

$L =$ leaf nodes

$I =$ internal nodes

$n =$ total nodes $= L + I$

In a tree no. of edges  $= n - 1$

All edges are produced by only internal nodes so, 

$k\times I = n-1\qquad \to(1)$   (for $k-ary$ tree, in this question $k = 3$)

$L + I = n\qquad \to (2)$

Here, given options are in terms of "n". So, eliminating $I$ from $(1)$ and $(2)$,

$L = ((k-1)n+1)/k$

you get $L = (2n+1)/3$

Answer is D.

Comments

please explain why k*I = T-1 ??

---

since the tree is k-ary tree, each internal node will have k branches contributing total of k*I internal branches which is equal to total number of branches or edges in the tree which is n-1

Answer 2

A Different way to solve the same Question

Total no of nodes in rooted tree is n .And every node is going to have either 0 children or 3 children a/c to the question .

        

Total no of nodes	Leaf Nodes	n/2	(n-1)/3	(n-1)/2	(2n+1)/3
n = 4 (figure 1)	3	2	1	3/2	3
n = 7 (figure 2)	5	7/2	2	3	5
n = 10 (figure 3)	7	5	3	9/2	7
n = 13	9	13/2	4	6	9
n = 16	11	8	5	15/2	11

Option D satisfy all the condition of the question .So option D is the answer .

Comments

Yap, trial and error method.

Answer 3

total number of nodes (n)  = internal nodes(i )  +  leaf nodes(L) 

total number of nodes (n) =  3 * nodes with three children (x)  + 1 

n = 3*x + 1 

x = (n-1)/3

n = i +L

L = n-i

L = n - (n-1)/3

L = (2n+1)/3

Comments

total number of nodes (n) =  3 * nodes with three children (x)  + 1 

How'd you get this?

---

 Mizuki 

it is because             no of node with 3 children means internal node and every internal  node have 3 children  so total children is 3*nodes with three children 

so total node is= 3 * nodes with three children (x)  + 1 

why we add 1  ?

because the root node in not the child of any node which in not counted in 3*nodes with three children (x) 

---

Thanks! @Gurdeep Saini

---

Nice answer

Answer 4

We know no of leaf nodes(l) in a k-ary tree (l) = i(k-1)+1 (i represents internal nodes)

here k=3 so l=i(3-1)+1==>l=2i+1==>l-2i=1----------(a).

and we know total no of nodes in a tree (n) = Leaf nodes(l)+internal nodes(i)

so n=l+i;==>(b).

Add (a) & (b)

               (a)---->l-2i=1

          2*(b)---->2l+2i=2n

_________________________

3l=2n+1===> so l=(2n+1)/3;

Answer 5

Any n-ary tree in which every node has either 0 or n children will take L=(n-1)*I +1
Given data n=3.
L=(3-1)I +1 =2I +1 -------> 1

 To find total number of nodes is nothing but sum of leaf nodes and internal nodes
N=L+I -------> 2
With the help of 1 and 2, we get L =(2n+1)/3.

Answer 6

Another Approach -

$N$ = Total nodes
$L$ = Leaf nodes
$I$ = Internal nodes

No. of leaves of full n-ary tree(0 or n children) = $I\times(n-1)+1$

here, n=3

Also, $N=I+L$

Thus, $I=N-L$

$L=(N-L)\times(3-1)+1$

$L=2N-2L+1$

$3L=2N+1$

$L=\frac{2N+1}{3}$