Exercise In doing this exercise, you may assume that all the keys in a binary search tree are distinct, i.e., that no two are equal. Let x be a node in a binary search tree.

1,2,3.?

1. If a is an ancestor of x and a key > r. key, then for any descendant d of r, we have a. key > d. key. 2. If a is the successor of r, then a is either an ancestor or descendant of r. (Hint: use the result of Exercise 1.6.) 3. If the right subtree of r is nonempty, then the successor of r is just the leftmost node in the right subtree. (Hint: use the previous result.) 4. If the right subtree of r is empty, and if r has a successor y (i.e., r is not the largest element in the tree), then y is the lowest ancestor of x whose left child is also an ancestor of r. (Hint: again use part 2 of this exercise.) 5. If x has a right child, then the successor of r does not have a left child. 6. Similarly, if x has a left child, then the predecessor of r does not have a right child