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, v, left, right, parent) 1: w+ 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 Troot = 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. 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