GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
156 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 (56.2k points)   | 156 views

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.2k 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
Top Users Jan 2017
  1. Debashish Deka

    8126 Points

  2. sudsho

    5042 Points

  3. Habibkhan

    4706 Points

  4. Vijay Thakur

    4458 Points

  5. Bikram

    4348 Points

  6. saurabh rai

    4212 Points

  7. Arjun

    4010 Points

  8. santhoshdevulapally

    3722 Points

  9. GateSet

    3292 Points

  10. Sushant Gokhale

    3286 Points

Monthly Topper: Rs. 500 gift card

19,122 questions
24,033 answers
52,725 comments
20,276 users