. Let T be a binary search tree. Suppose we want to include a field 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 fields in T. What is the running time of your algorithm?

b. Now suppose we make modifications to T by inserting or removing items. For each modification i.e., an insertion or a removal describe the modifications that have to be made to the size fields of the nodes in T. How much time will such modifications 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 fields 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 fields of the nodes in the tree.

Dictionari ies and Binary Search Trees ordered 145 1.2 Binary Search Trees The data s cture we discuss in this section, the binary search tree, applies the motivation of the binary search procedure to data structure. We define ree to be a binary tree in each internal node v stores an a binary search which element such that the elements stored in the left subtree of v are less than or equal ro e, the stored in the right subtree of v are greater than or equal to e Furthermore, assume that external nodes store no elements; hence, they could n fact be null or references to a NULL NODE objec a An inorder traversal of a binary search tree visits the elements stored such tree in nondecreasing order. A binary search tree in the question asked at each internal supports searching, where equal to, or larger than the node is whether the at that node is less than, element being searched for by we can use a binary search tree T to locate an element with a certain value x current node down the tree T. At each internal node we compare the value of the the search search element x. If the answer to the question is Smaller. search continues in the left subtree. If the answer is equal," then the in the successfully. If the answer is "greater," then the search continues search subtree. Finally, if we reach an external node (which is empty), the terminates unsuccessfully. (See Figure Figure 3.4: A binary search tree storing integers. The thick solid path drawn with thick lines is traversed when searching (successfully) for 36. The thick dashed path is traversed when searching (unsuccessfully) for 70