The Gateway to Computer Science Excellence
+14 votes
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)$.
in DS by | 1.6k 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

number of leaves =internal node (number of k-array tree-1)+1it should ne 2n+1

2 Answers

+12 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}$


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.
edited by

Apart from proving it by induction 

I was wondering does this formula hold correct ?


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.
I think questions is wrong because here say no of leaves node 2n-1 but if 1 internal node than 3 leaves but here with 2n-1 = 0

I think correct answer is 2n+1
0 votes
The question is wrong . Since the Question asks for "A 3−ary3−ary tree is a tree in which every internal node has exactly three children".

Proof :

N3 : Number of internal nodes with 3 children

N0 : Number of nodes with 0 children i.e. number of leaves

N : Total number of nodes

1) According to the question , since a node can only have 3 children or none this means , N = N3 + N0

2) Every node with 3 children will contribute to 3 edges connecting nodes to the next level , 3 * N3 = E (Total edges) = N - 1 (edges of a tree)

Now solving N = N3 + N0 and 3 * N3 = N - 1 we get N0 = 2 * N3 + 1 (Ans)

hence then answer should have been 2*n + 1 and not 2 * (n - 1)
edited by

Related questions

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
52,345 questions
60,484 answers
95,289 users