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**

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)$.

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

$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.

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.

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

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)

52,345 questions

60,484 answers

201,814 comments

95,289 users