QUESTION 1In a Binary Search Tree (BST), the predecessor of a node x is defined as the node with the largest key smaller than x.key. Write a pseudocode that returns the predecessor of a node x. Assume all keys in the tree are distinct. What is the worst-case running time of your algorithm?QUESTION 2Consider the binary search tree (BST) below, where each node has a label. Note that the label is NOT the key. The keys satisfy the BST property. Assume that all the keys are distinct.QUESTION 3Let T be a binary search tree (BST) with n keys. Select all the statements below which are TRUE.• If T is a perfectly balanced BST (all leaves have the same depth), then the depth of all nodes is O(lg n)• The height of T is O(lgn)• Tree-insert, tree-delete, and tree-search have the worst-case running time O(n)• INORDER-TREE-WALK(T.root) prints the keys in monotonically increading orderQUESTION 4Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is p = < 7, 2, 8, 4, 5 >. Show the m and s tables and the printing of an optimal parenthesization. Use the algorithm learned in class.QUESTION 5Consider the matrix chain A2A3A4, where A2 has dimension 10 × 20, A3 has dimension 40 × 60 and A4 has dimension 60 × 10. Which of the following parenthesizations require the minimum number of scalar multiplications?• This chain of matrices cannot be parenthesized because the sequence of matrices is incompatible• All parenthesizations have the same number of scalar multiplications• ((A2A3)A4)• (A2(A3(A4))