2. 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 o receives the name oL and any node that is the right child of that node receives the name oR. Give a recurrence relation returning the number of R's in all labels of all nodes. For example, the following tree has 10 R's. 1 RL FR LLL LLR PLR RRR Hint: For a node v, let f(u) be the number of R's in the tree rooted at v, if the naming started at v. Also, let (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 give a recurrence relation for f(v)