GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
328 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 (66.2k points) 1154 2199 2523 | 328 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

+5 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 (32.9k points) 45 230 468
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
i should be height otherwise it has 3 nodes at 1st level also .bcoz level = height +1.


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
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8280 Points

  4. srestha

    6300 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4352 Points

  9. sushmita

    3970 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Popular Question sh!va
Popular Question sh!va
Regular Rishabh Gupta 2
Popular Question Sunil8860
Reader Rajesh Veeranki 2
Notable Question rahul sharma 5
Commentator Shivam Chauhan
Notable Question set2018
Nice Comment srestha
Notable Question set2018
27,325 questions
35,177 answers
84,124 comments
33,280 users