BINARY SEARCH TREE

2. [4 pts.] Complete the pseudocode of the successor function for a BST, started for you in the partial pseudocode given in Algorithm 6, by writing down the only two missing statements (in line indexes 9 and 14). The function outputs the node y with the next key in the order sequence following that of node w with respect to the BST, or NULL if w has the largest key.

Using big-Oh notation, provide a tight worst-case running time of the method as a function of the number of nodes n in the BST containing w.

Algorithm 6 successor(w) 1: if w NULL then 3: else 4: if w.right NULL then yr.parent while yNULL and y.right-x do 6 7: 8: 9: 10: end while else 12: 13 14 15 16: 17: end if 18: return y while y.rightNULL do end while end if