Question

1. Consider the following binary search tree:

1. What tree results after you insert the nodes 44, 48, 32, 36, 38, and 49 in that order? You only need to show the final result.
2. Given the original tree, what tree results when you delete the node 43 and then node 50?  (Note: there may be more than one correct answer, but please choose only one).
1. If you delete an item from a binary search tree and then immediately insert it back into the tree, will you always end up with the same tree? Briefly justify your answer.
2. Suppose that we have a set of unique numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? Only explain the invalid cases (no need to explain the others).
   1. 2, 252, 401, 398, 330, 344, 397, 363
   2. 924, 220, 911, 244, 898, 258, 362, 363
   3. 925, 202, 911, 240, 912, 245, 363
   4. 2, 399, 387, 219, 266, 382, 381, 278, 363
   5. 935, 278, 347, 621, 299, 392, 358, 363

c.Write the following method which tests if a BinaryTree is a binary search tree. Assume this method exists in the BinaryTree class. Note: Empty binary trees should also be considered to be binary search trees.

public boolean isBinarySearchTree()
// post: returns true iff this is a binary search tree