GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
175 views
A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n$ internal nodes is $2(n-1)$.
asked in DS by Veteran (58.2k points)   | 175 views

I think in the question, number of leave nodes(L) for n internal nodes in a 3 ary tree is

 L= 2(n-1) + 3 = 2n+1

1 Answer

+4 votes
No of nodes at level $i =3^i$

Let height of tree be $h$

So total no of internal nodes $=3^0+3^1+3^2+\dots +3^{h-1}=\frac{3^{h}-1}{2}$

$2n=3^{h}-1$

No of leaf nodes $=3^h =2n+1=2(n-1)+3$

Let us prove by induction

Base case

$n=1$ (one internal node i.e., root node)

No of leaves $=2(1-1)+3=3$

Let it be true for $n$ internal nodes

Now we prove for $m$ nodes where $m=n+1$

We have $L(m)=2(n+1-1)+3$

Also $L(m)=L(n)+3-1\\=2(n-1)+3+3-1\\=2n+3$

So if $L(n)$ is true then $L(n+1)$ is also true

Hence proved by induction.
answered by Veteran (30.7k points)  
edited by

Apart from proving it by induction 

I was wondering does this formula hold correct ?

eg 

n = 2 L= 5

but by L = 2(n-1) = 1 ???????? How is it correct

let there be n internal nodes (including root)  and L leaves

then using degree 

(n-1)4 + 3 + L = 2( n+L-1)

L= 2n + 1

eg in above pic n = 2 so L = 5

(Just trying to learn calculating no of leaves - not worrying about proving by induction .....just want to know if formula is correct ? )

As per the wordings given in question your tree is correct. But i guess they meant a full ternary tree- otherwise no. of leaves cannot be a fixed value.
Can u plz draw a tree @arjun sir where the question's no. of leaf requirement will satisfy?

I m not getting any..
@Arjun ...i think question is wrong
Members at the site
Top Users Feb 2017
  1. Arjun

    4676 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,532 comments
21,923 users