3. Let T be a binary search tree. Suppose we want to include a eld v.size, the number of items stored in the subtree of v, at each node v. a. Given T, describe an algorithm that will populate all the size elds in T. What is the running time of your algorithm?

b. Now suppose we make modications to T by inserting or removing items. For each modication i.e., an insertion or a removal describe the modications that have to be made to the size elds of the nodes in T. How much time will such modications take?

c. Using the binary search tree on Figure 3.4, insert an item with key equal to 52 and show the changes that have to be made on the size elds of the nodes in the tree. Now, remove the item with key equal to 75. Again, show the changes that have to be made on the size elds of the nodes in the tree.