Notice that the tree has 4-way branching and the problem size decreases by a factor of 3 at each level.
(a) There are \(4^5\) nodes in the fifth level of the tree.
(b) Each node in the fifth level contains the value \(n/3^5\). So the sum of all the nodes in the fifth level is \(4^5 \cdot n /3^5 = n(4/3)^5\) .
(c) The height of the tree is the level of the leaves. We reach the leaf level when \(n/3^k\) equals the input for the base case, which is 9. So we need to solve \(n/3^k = 9\) for k.
\(n/3^k = 9\) is equivalent to \(n = 3^{k+2}\). That is \(\log_3 n = k+2\). So \(k = \log_3 n-2\).
So the height of the tree is \(h = \log_3 n-2\).
(d) Since the branching factor is 4, there are \(4^h\) leaves. That is, \(4^{\log_3 n-2}\) leaves
Simplifying this, we have \(4^{\log_3 n-2} = \frac{1}{16}4^{\log_3 n}\). But \(4^{\log_3 n} = 4^{\log_4 n \log_3 4} = (4^{\log_4 n})^{\log_3 4} = n^{\log_3 4}\) So the number of leaves is \(\frac{1}{16}n^{\log_3 4}\)