1.) For the set A = {1, 2, 3, 5, 8, 13, 21} of keys, draw three binary search trees of different heights.

2.) Suppose that we have numbers between 1 and 1000 in a binary search tree, and we

want to search for the number 363. Which of the following sequences could not be

the sequence of nodes examined? Explain why.

363. 2, 252, 401, 398, 330, 344, 397, 363.

364. 924, 220, 911, 244, 898, 258, 362, 363.

365. 925, 202, 911, 240, 912, 245, 363.

366. 2, 399, 387, 219, 266, 382, 381, 278, 363.

367. 935, 278, 347, 621, 299, 392, 358, 363.

3.) For a binary search tree T of n nodes, determine the number of internal nodes in O(n) running time in psuedo code.

(1) Give a recursive algorithm.

(2) Give a non-recursive algorithm.

4.) Given a Binary Search Tree T and two integers a and b on the tree, print all elements in T between a and b in psuedo code.

5.) Suppose that instead of each node x keeping the attribute x:p, pointing to xs

parent, it keeps x:succ, pointing to xs successor. Give pseudocode for SEARCH,

INSERT, and DELETE on a binary search tree T using this representation. These

procedures should operate in time O(h), where h is the height of the tree T . (Hint:

You may wish to implement a subroutine that returns the parent of a node. This is the same question of 12.3-5 in the textbook.)