The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
832 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 (59.6k points) | 832 views
+6

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
number of leaves =internal node (number of k-array tree-1)+1it should ne 2n+1

1 Answer

+10 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 Boss (31.8k points)
edited by
+3

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 ? )

0
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.
0
Can u plz draw a tree @arjun sir where the question's no. of leaf requirement will satisfy?

I m not getting any..
+2
@Arjun ...i think question is wrong
0
i should be height otherwise it has 3 nodes at 1st level also .bcoz level = height +1.

Related questions

+1 vote
1 answer
4
asked Jan 22, 2017 in DS by Devwritt Active (3.2k points) | 846 views
+3 votes
3 answers
5


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

42,699 questions
48,660 answers
156,587 comments
63,969 users