GATE CSE 1994 | Question: 5

Question

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

Comments

Question :

“A 3−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−ary tree with n internal nodes is 2(n+1).

 

I think it must be 2n+1. anyone verify….

---

yes it must be 2n+1 instead of 2(n+1).

Answer 1

Number of nodes at level $i =3^i$

Let height of the tree be $h$

So total no of internal nodes, $n=3^0+3^1+3^2+\dots +3^{h-1}=\frac{3^{h}-1}{2}$

$2n=3^{h}-1$

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

Comments

@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

Answer 2

Lets try to get the formula by forming the recurrence relation.
Let T(n) denote the number of leaves of a 3 ary tree having ‘n’ internal nodes.
Base case : T(1) = 3
Now if we take one of the leaf nodes and convert it to internal node by adding 3 children to it, then no of leaves would decrease by 1 (since one leaf got converted to internal node) and also increase by 3(owing to the 3 new leaves created by leaf which converted to internal node)
So now T(n)=T(n-1)+3-1
                    =T(n-1)+2
                    =T(n-2)+2*2
                    =T(n-3)+3*2
                    ……
                   =T(n-k)+k*2

 when n-k=1, k=n-1, also T(n-k)=T(1)=3

                   =3+2*(n-1)
                   =2n+1

Answer 3

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)