5. [15 pts.] Consider a version of a binary search tree (BST) for sorted maps with integer keys that stores additional information as data members of each node w of the tree to account for the smallest and largest integer keys in the subtree rooted at w. Suppose that we can access this information using w.min, for the smallest integer key, and w.max, for the largest. Algorithm 4 provides the pseudocode for the constructor of a node in a binary tree with the additional information.

Algorithm 4 Node(k,v,left,right,parent)

1: w new node

2: w.key k

3: w.value v

4: w.left left

5: w.right right

6: w.parent parent

7: w.min k

8: w.max k

9: return w

(One can adapt the find operation to account for this information and potentially stop the search early. Algorithm 5 provides the pseudocode for the new implementation of the find function.)

Algorithm 5 find(T,k)

1: w T.root

2: while w 6= NULL and k 6= w.key do

3: if k < w.min or k > w.max then return NULL

4: if k < w.key then

5: w w.left

6: else

7: w w.right

8: return w

(Note that the data structure must maintain the invariant w.min w.key w.max. Hence, both the insert and delete operations must be properly adapted.)

(Your task is to complete the pseudocode for the insert function, started for you in the partial pseudocode given in Algorithm 6, by writing the missing statements.)

(NOTE: The missing statements you are asked to write for the insert function in Algorithm 6 only require simple accesses or changes to node ws data members or appropriate reassignment of the variable w itself.)

Algorithm 6 insert(T,k,v)

1: w T.root 2: while w 6= NULL and k

6= w.key do

3: 4:	if k < w.min then
5: 6:	if k > w.max then
7:	if k < w.key then
8:	if w.left = NULL then
9: 10:	x Node(k,v,NULL,NULL,w)
11: 12:	return x
13:	else
14:	if w.right = NULL then
15: 16:	x Node(k,v,NULL,NULL,w)

17:

return x

18:

19: if w 6= NULL then

20:

21: return w