This is not a programming assignment. Write code or pseudocode Let the BinarySearchTree class be defined as follows: class BinarySearchTree f class Tree ( int element; Tree left, right; Tree (int x, Tree l, Tree r) I element -x; left = 1; right - r; Tree root; // root of binary search tree int size;// number of elements in the BST BinarySearchTree) // constructor root null; size - 0; BinarySearchTree (Tree t, int s)// constructor root t; size s 1. Given a sorted array of integers, write an algorithm to build a height-balanced binary search tree with its elements. Analyze the running time of the algorithm Recursive algorithms can be solved using the Master method. The functions that you need to write are the following. // Build a height-balanced BST from arr[0..arr. length-1] BinarySearchTree arrayToBST(int[] arr) /*To do*/h // Helper function to build a tree from a subarray // Recursive algorithm that builds a tree recursively from the elements of arrlp..r] // Returned tree is balanced, and satisfies the order constraints of a BST Tree arrayToTree (int[ arr, int p, int r) /* To do */ }
2. Given a binary search tree of integers, and an integer x, write the functions floor and ceiling. Hint: If x is not in the tree, the floor and ceiling elements are on the path taken by find(x) // Class to store 2 integers class Pair { int floor, ceiling; Pair ( int f, int c) { floor = f; ceiling = c; } } // Floor: largest element of the BST that is less than or equal to x // Ceiling: smallest element of the BST that is greater than or equal to x Pair floorAndCeiling(BinarySearchTree t, int x) To do */ }