Exercise 7        Name __________________        Score __/ 14
Document last modified: 

1. (2) For the set of keys {1, 4, 5, 10, 16, 17, 21} draw the binary search trees of height 2 and 3.

    

2. (4) Exercise 12.1-3 The part using a stack. Hint: Use a boolean variable to track whether the left subtree has been traversed.
3. (4) Give recursive algorithms that perform preorder and postorder tree walks in Q(n) time on a tree of n nodes.
4. (2) Exercise 12.2-1

   Suppose that we have the 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? Mark the first number in error.

   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

    

5. (2) Exercise 12.3-1