## Description

1. Binary search tree

(a) Suppose that we insert a sequence of keys 4, 9, 2, 5, 1, 7, 6, 3, 8 into an initially

empty binary search tree. Draw the resulting tree.

(b) Suppose that we further delete the key 5 from the tree you get in Problem (1a).

Draw the resulting tree.

(c) Suppose that we further delete the root from the tree you get in Problem (1b).

Draw the resulting tree.

2. Given a binary tree, in which each node is associated with an integer key, it may not

possess the binary search tree property. Describe a most runtime-efficient algorithm

that determines whether such a tree is indeed a binary search tree. Also, tell us what

the runtime of your algorithm is. Show us why your algorithm is a most runtimeefficient one.

Note: You can describe your algorithm in English. However, if you find that writing

pseudo-code/code is helpful for your illustration, feel free to do so.

3. Suppose the node of a binary search tree is defined as follows.

struct node {

Key key; // key

node* left; // left child

node* right; // right child

};

Implement the following function which gets the predecessor of a given key in the tree:

node* getPred(node* root, Key key);

// REQUIRES: The tree rooted at “root” is non-empty.

// “key” is in the tree rooted at “root”.

// EFFECTS: Return the predecessor of “key” in the tree rooted at “root”.

// Return NULL if there is no predecessor

1

You can assume the following function is availabe:

node* findMax(node* root);

// REQUIRES: The tree rooted at “root” is non-empty.

// EFFECTS: Return the node with the maximal key in the tree rooted

// at “root”.

4. Suppose nodes A, B, …, J are located on a 2-D plane shown in Figure 1. We insert

these nodes in the order A, B, …, J into a k-d tree. Show the final tree. Assume the

comparison dimension of the root is the x dimension.

B (8,38)

A (40,80)

F (13,92)

x

y

C (18,26)

D (75,42)

G (22,58) E (90,54)

H (60,88)

I (50,20)

J (100,24)

Figure 1: The locations of a number of nodes in a 2-D plane.

2