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(w, k) 2: while w+ NULL do 3: if w.key = k then return w if w.key > k then # B else Statement # Operation Statement 1 w w.left Statement 4 return u Statement 6 w w.right Statement 8 ut w Statement 9 Algorithm 1 NODE(k, v, left, right, parent) 1: wt new node 2: w.keyk 3: w.value v 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 v 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, k) 1: if T.root = NULL then return NULL 2: w+ FINDNODE(T.root, k) 3: if w.key = k then return w.value 4: return NULL The function FINDNODE 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. 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(w, k) 2: while w+ NULL do 3: if w.key = k then return w if w.key > k then # B else Statement # Operation Statement 1 w w.left Statement 4 return u Statement 6 w w.right Statement 8 ut w Statement 9 Algorithm 1 NODE(k, v, left, right, parent) 1: wt new node 2: w.keyk 3: w.value v 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 v 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, k) 1: if T.root = NULL then return NULL 2: w+ FINDNODE(T.root, k) 3: if w.key = k then return w.value 4: return NULL The function FINDNODE 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
