The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3k 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 by Veteran (59.5k points)
edited by | 3k views

5 Answers

+32 votes
Best answer

$L =$ leaf nodes

$I =$ internal nodes

$T =$ total nodes $= L + I$

in a tree no. of edges  $= T - 1$

all edges are produced by only internal nodes so 

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

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

Solving $(1)$ and $(2)$ we get

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

So put $k = 3, T = n$

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

Answer is D.

answered by Boss (13.5k points)
edited by
0
please explain why k*I = T-1 ??
+12 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.1k points)
0
Yap, trial and error method.
+9 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)
+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)
0 votes

Let "h" be height of the 3-ary tree.

Since we know that Leaves are present at last level (in case of maximum number of leaves like in Complete 3-ary tree).

So, number of Leaves (say L) will be "atmost" = 3h.

ex- we can have a maximum of  L=1 at h=0 (when root itself is leaf)

  L=3 at h=1

  L=9 at h=2 and so on. 

Similarly, Internal nodes are present in maximum at (h-1) height.

So,Number of Internal Nodes (say I) will be "atmost "      

=30+31+32+.........3h-1 3(h  -1)/2

Let n be Total number of nodes, then n= L+I

n= 3h +  3h -1/2

n= 3h+1 -1/2

2n+1=3.3h

2n+1=3.L  ( since L= 3h)

hence L= (2n+1)/3

answered by Active (1k points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,176 questions
45,681 answers
132,628 comments
49,581 users