data structure tree doubt

Question

A 5-ary  tree is a tree in which every internal node has 3 children.The number of leaf nodes in such a tree with 10 internal nodes is______

Answer 1

Here we need 2 equations ,

a) No of edges = No of vertices - 1 [ Basic definition of tree ]

b) Handshaking theorem i.e. sum of degree = 2 * no of edges

Say no of leaf nodes = x

Hence sum of degree due to leaf nodes = x

Now for non root nodes , degree = 4 as 1 due to parent and 3 due to 3-ary ness of tree..

For root node , degree = 3..

Hence ,

        Sum of degree =  2 * no of edges

==>  3 + 9 * 4 + x  =  2 * ( x + 10 - 1 )   [ As no of edges = no of vertices - 1 and no of vertices = x + 10 ]

==>  39 + x  =  2x + 18

==>  x   =  21

Hence no of leaf nodes = 21

Comments

sorry there is correction to this question it's not 3-ary tree it's a 5-ary tree..now what will be the answer....??

---

This is not the definition of 5-ary tree..This is the ACE test series question and they are known for their miracles..

N u also following the same..

Answer 2

in any n array tree

total no. of nodes = i*n + 1 where i is the no. of internal nodes , one for the root node

now Total nodes = 10*3+1 = 31

we can also write total nodes as (No. of leaf nodes(L) + No. of internal nodes(i))

hence L+i=31

L=31-i

  =31-10

  =21 is the answer

Comments

what about that formula..if we go like that..

---

then also u will get 21 in case of 3 ary tree

but someone has changed it to 5 array in the question

then answer should be 41

---

yeah I got 41 and they have given 5-ary tree...so is it correct answer??