Test by Bikram | Mock GATE | Test 3 | Question: 21

Question

A ternary tree is a tree in which every internal node has exactly three children.

The number of leaves in a ternary tree with $’z’$ internal nodes is _______.

• A. $2$$\left ( z+1 \right )$$+ 3$
• B. $2z$
• C. $3z$
• D. $2z + 1$

Comments

Here we can use  sum of degree= 2* number of edges 

Now in a terneray tree we have root of degree 3 , non root internal node of degree 4 ( 1 indegree+3 outdegree) and leaves of degree 1(indegree as 1).

so sum of degree = 3R + 4Z +1L where R=root , Z=non root internal nodes, L =leaves . Also R=1 here

    sum of degree = 3+4Z+L               --------------------------------(1)

Now in a tree ,no of edges= number of nodes -1=[1 ( for root) + Z + L ]-1 =Z+L

   |E|        =  Z + L            ------------------------------(2)

substituting 1 and 2 in above formula yields

      3+4Z+L=2(Z+L)

==> 3+4Z+L-2Z=2L

==>  L=2Z+3

I know this differ from the options . I cant find where i m going wrong in this question..Please review my solution .

Answer 1

Key Idea  - The degree of a node = the number children of that node . 

Total number of nodes = Internal Nodes + Leaves  = z + L.

Also , Total Number of nodes = Internal Node * deg of Internal Node + Leaves *deg of Leaves + 1 ( Root Node)

                                           =  z*3 + L*0 + 1.

On equating the two L = 2z + 1

Comments

Total Number of nodes = Internal Node * deg of Internal Node + Leaves *deg of Leaves + 1 ( Root Node)

Can you tell us where this formula comes from?

Answer 2

Option D) is correct answer

---

Let total number of nodes= $N$

Number of internal nodes= $z$

Number of leaves= $L$

Given a ternary tree in which each internal node has exactly 3 nodes.

$N=3*z+1$ ......(i)

Also $N=z+L$ .......(ii)

On solving (i), (ii)

$L=2z+1$