2. (10 pts. Consider a general linked-structured binary search tree (BST) implementation for the sorted map ADT. (Note that general BSTs may not satisfy the height-balance property.) Algorithm 1 provides the pseudocode for the constructor of a node in a BST. Algorithm 1 NODE(k. u, left, right, parent) 1: new node 2. w.keyk 3: w.value 4: w.left left 5. w.right right 6: w.parent parent 7: return w Algorithm 2 provides the pseudocode for an implementation of the FIND function. It takes as input a BST T with root node T.root and a key k, and outputs the value associated with key k in the sorted map, or NULL if the map does not contain that key. It uses the function FINDNODE Algorithm 3 on next page, still incomplete) as an auxiliary method. Algorithm 2 FIND(T. ) 1: if T.root = NULL then return NULL 2: FIND NODET.root. k) 3: if w.key = k then return w.value 4: return NULL The function FIND NODE takes as input a non-NULL node w in the tree and a key k, and outputs the last node visited during the search: that is, either (1) a node w in the tree with the key k or (2) the last node considered during the search if no node with key k was found. It assumes that it is the responsibility of the calling function to determine whether the search was successful or not by checking whether the output node contains the key k or not. Page 3 of 7 Homework 2 CIS 350: Data Structures and Algorithm Analysis Winter 2020 Complete the pseudocode for the algorithm FINDNODE (Algorithm 3) by matching each missing statements number-listed on the left-hand side below, with a corresponding operation, listed on the right-hand side below. (Note that the same operation on the right may match multiple statements on the left.) Algorithm 3 FINDNODE.) 2. while w+ NULL do 3: if key = k then return w 5: if w.key > k then else Statement # Operation Statement 1 w w .left Statement 4 return u Statement 6 W w .right Statement 8 Statement 9 Write down tight big-Oh characterizations of the worst-case running time and space complex- ity of the implementation of the FIND method Algorithm 2) as a function of the number of nodes n in the general) BST. Time Space 2. (10 pts. Consider a general linked-structured binary search tree (BST) implementation for the sorted map ADT. (Note that general BSTs may not satisfy the height-balance property.) Algorithm 1 provides the pseudocode for the constructor of a node in a BST. Algorithm 1 NODE(k. u, left, right, parent) 1: new node 2. w.keyk 3: w.value 4: w.left left 5. w.right right 6: w.parent parent 7: return w Algorithm 2 provides the pseudocode for an implementation of the FIND function. It takes as input a BST T with root node T.root and a key k, and outputs the value associated with key k in the sorted map, or NULL if the map does not contain that key. It uses the function FINDNODE Algorithm 3 on next page, still incomplete) as an auxiliary method. Algorithm 2 FIND(T. ) 1: if T.root = NULL then return NULL 2: FIND NODET.root. k) 3: if w.key = k then return w.value 4: return NULL The function FIND NODE takes as input a non-NULL node w in the tree and a key k, and outputs the last node visited during the search: that is, either (1) a node w in the tree with the key k or (2) the last node considered during the search if no node with key k was found. It assumes that it is the responsibility of the calling function to determine whether the search was successful or not by checking whether the output node contains the key k or not. Page 3 of 7 Homework 2 CIS 350: Data Structures and Algorithm Analysis Winter 2020 Complete the pseudocode for the algorithm FINDNODE (Algorithm 3) by matching each missing statements number-listed on the left-hand side below, with a corresponding operation, listed on the right-hand side below. (Note that the same operation on the right may match multiple statements on the left.) Algorithm 3 FINDNODE.) 2. while w+ NULL do 3: if key = k then return w 5: if w.key > k then else Statement # Operation Statement 1 w w .left Statement 4 return u Statement 6 W w .right Statement 8 Statement 9 Write down tight big-Oh characterizations of the worst-case running time and space complex- ity of the implementation of the FIND method Algorithm 2) as a function of the number of nodes n in the general) BST. Time Space