Duplicates in an ADT could mean either identical items or, more subtly, objects that match because their class overloads the equality operator so that it compares only certain fields, while differences exist in other fields. If duplicates are allowed in a binary search tree, it is important to have a convention that determines the relationship between the duplicates. Items that duplicate the root of a tree should either all be in the left sub tree or all be in the right sub tree, and, of course, this property must hold for every sub tree.
a. Why is this convention critical to the effective use of the binary search tree?
b. This chapter stated that you can remove an item from a binary search tree by replacing it with the item that either immediately follows or immediately precedes the item to be deleted. If duplicates are allowed, however, the choice between in order successor and in order predecessor is no longer arbitrary. How does the convention of putting duplicates in either the left or right sub tree affect this choice?