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
