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

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}}
\]

 

Answer 2

 

Answer : D . (2n+1)/3