Note: In this problem, you'll be writing $-$ but not solving $-$ a recurrence

relation over a data structure. When we get to dynamic programming

in class, we'll see how to solve these types of recurrences.

Consider a rooted binary tree with nodes are labelled as follows. The

root node is labelled with the empty string. Then, any node that is a

left child of a node with name $$ receives the name $L$ and any node

that is the right child of that node receives the name $R.$

Give a recurrence relation returning the number of $R\text{'}$s in all labels of

all nodes. For example, the following tree has $10R\text{'}$s$.$

Hint: For a node $v,$ let $f(v)$ be the number of R$\text{'}$s in the tree rooted

at $v,$ if the naming started at $v.$ Also, let $l(v)($resp$.r(v)$ be the left $($resp$.$ right$)$ child of v if it exists or NULL otherwise. Finally, let s$($v$)$ be the number of nodes in the subtree rooted at v and assume this value is stored at each node. Now write a recurrence relation for f$($v$).$ Don$$t forget to include the base case and to test it on some examples.