UGC NET CSE | December 2018 | Part 2 | Question: 26

Question

In a ternary tree, the number of internal nodes of degree $1, 2, $ and $3$ is $4, 3$, and $3$ respectively. The number of leaf nodes in the ternary tree is

• A. $9$
• B. $10$
• C. $11$
• D. $12$

Comments

can also be answered by making a tree  ans 10

---

are the values correct? because i'm getting sum of degree of vertices to be odd , which is not possible .

---

@prashant jha 1

I think in the question number of children of internal nodes are given, not the degree.

so you can not say that sum of the degree of vertices to be odd. for that, we have to find the degree of all the vertices

 

Answer 1

By seeing the degree's of nodes, i understood TREE assumed as Directed graph.

Let N$_i$ represent Number of Nodes with Degree i

Total No.of Nodes in a Tree = N$_0$ + N$_1$ + N$_2$ + N$_3$

In a tree with N nodes have exactly n-1 edges.

∴ N = |E| + 1 ==> N$_0$ + N$_1$ + N$_2$ + N$_3$ = |E| + 1  --------- (1)

Given that, N$_1$ = 4 , N$_2$ = 3 ,  N$_3$ = 3

Total Edges in the directed graph = summation of all degrees = ∑ N$_i$ . i

∴ | E | = ( 0*N$_0$) + (1*N$_0$) + (2*N$_2$) + (3*N$_3$) = ( 0*$\color{red}?$) + (1*4) + (2*3) + (3*3) = 0+4+6+9 = 19

Substitute this value in eqn (1),

N$_0$ + N$_1$ + N$_2$ + N$_3$ = 19 + 1

N$_0$ + 4+3+3 = 19+1 ===> N$_0$ + 10 = 20 ===> N$_0$ = 10

Comments

is it in digree or out digree,

digree of a node=in digree+out digree ?

Answer 2

we all know, the tree is also an acyclic graph.

so we can simply apply the concept:

SUM OF DEGREE OF ALL THE VERTICES = 2 X (TOTAL  NUMBER OF EDGES)

in the question, it is given that,

nodes with degree 1 == 4 (that means there are 4 nodes having 1 child, i.e degree = 1+1 = 2)

nodes with degree 2 == 3(that means there are 3 nodes having 2 child, i.e degree = 2+1 = 3)

nodes with degree 3 == 3(that means there are 2 nodes having 3 children (so degree == 3 + 1 = 4) and 1 root node with degree 3(number of children and because ternary and root has no parent--> degree == 3 + 0 = 3) )

Let,

      number of leafs nodes = L

    and degree of all leafs node is 1 because it is attached with its parent i.e one edge

     total nodes in tree = internal nodes + leafs node = 4 + 3 + 3 + L = 10 + L

so, total number of edges in tree = (total nodes - 1) = (10 + L) -1 = 9 + L 

SUM OF DEGREE OF ALL THE VERTICES = 2 X (TOTAL  NUMBER OF EDGES)

(1(root) X 3)  + ( 2 X 4 ) + (3 X 3)  + (4 X 2)  + ( L X 1) = 2 X [ 9 + L ]

=> 3 + 8 + 9 + 8 + L = 18 + 2L

=> 28 + L = 18 + 2L

=> L = 10

s0 answer (D)