Let T1 be the rooted tree consisting of a single root vertex. For n 2, let Tn be the rooted tree consisting of a root vertex with four children, where the subtree rooted at each child is the tree Tn1.

Let Ti be the rooted tree consisting of a single root vertex. For n 2 2, let Tn be the rooted tree consisting of a root vertex with four children, where the subtree rooted at each child is the tree T- (a) Calculate how many paths in Tn start from the root vertex and end at a leaf vertex. (b) What is the minimum number of bits (O's and 1's) required to represent a path in Tn 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 Tn 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 Ts using your method from part (c)