Question

Let T_1 be the rooted tree consisting of a single root vertex. For n greaterthanorequalto 2, let T_n be the rooted tree consisting of a root vertex with four children, where the subtree rooted at each child is the tree T_n - 1. (a) Calculate how many paths in T_n start from the root vertex and end at a leaf vertex. (b) What is the minimum number of bits (0's and 1's) required to represent a path in T_n that starts at the root vertex and ends at a leaf vertex? Show your work and simplify your answer as much as possible. (c) Describe how to encode a path in T_n that starts at the root vertex and ends at a leaf vertex using the number of bits you gave in part (c). (d) Encode the bold path in T_3 using your method from part (c).

Answer 1

a) number of paths is equal to number of children of root node *number of childeren of that node = 4*4 = 16.

b) number of minimum bits to represent the path:- four childeren can be represented with minimum of 2 digits and next childrens also with two digits so 2+2=4 bits. eg 0000 shows first path from.first children k1 of root and first children of k1.

c) we can encode a path of given tree as follows

1. encode the number if children of root i.e. in given tree, encoding of children is 00,01,10,11.

2. similarly subsequent children of these paths can be encoded.

d) for the bold path encoding is as follows:+

encode from root to first child - 01

encode from above child to leaf- 11,

so encoding is 0111.