+22 votes
3.1k views

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

1. $\frac{n}{2}$
2. $\frac{(n-1)}{3}$
3. $\frac{(n-1)}{2}$
4. $\frac{(2n+1)}{3}$
asked in DS
edited | 3.1k views

## 4 Answers

+34 votes
Best answer

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

answered by Boss (13.6k points)
edited
0
please explain why k*I = T-1 ??
0
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
+13 votes

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 .

answered by Boss (45.3k points)
0
Yap, trial and error method.
+10 votes

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

answered by Active (1.2k points)
0

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

How'd you get this?

+3 votes

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;

answered by (389 points)
Answer:

+45 votes
3 answers
1
+14 votes
2 answers
2
+14 votes
6 answers
3