Given a binary search tree of n nodes and its ADT defined below, answer the following questions. Binary Search Tree ADT isEmpty (root): Determine whether or not the binary tree with node root as the root is an empty tree. - left Child(root): Return the left child of node root. - right Child(root): Return the right child of node root. - parent(x): Return the parent of node x. - height(x): Return the height of the (sub)tree rooted at node x. - data(root): Return the data value in node root. - leftSize(root): Return the number of nodes in the left subtree of node root. - rightSize(root): Return the number of nodes in the right subtree of node root. (i). [6 marks] Show an algorithm in pseudo-code to find the maximum in the BST by using the above ADT operations. (ii). [6 marks] Show an algorithm in pseudo-code to check if a binary search tree is balanced or not by using the above ADT operations (Hint: Refer to CSCI2100C- Lecture11-12-Binary-Search-Tree Page 24 for the definition of balanced binary search tree). - (iii). [6 marks] Show an algorithm in pseudo-code to find the k-th (k n) largest element in the BST by using the above ADT operations. AG