must be coded in c++ without any STL libraries sadly :( so im struggling on this problem, any help would be greatly appreciated, thanks in advance! :) assignment is due tomorrow and im really struggling on this last question :(

a. Begin by implementing a BST for integers. The underlying structure is a linked list. You need these methods: i. BST(); -- Constructor ii. void put (int) Inserts a value into the BST. iii. Void put(int[] a) Inserts an entire array a into the BST. iv. int search(int key) Searches for a value in the BST. If found, return the key. If not found, return 0 and print Value not found! to the console. Additionally, print out the total number of comparisons needed (whether the key is found or not). v. int returnSize(); -- returns the total number of nodes in the BST. See Slides 3-10 on Binary Search Trees to see how a BST might be structured with these methods. The implementation is effectively the same as shown. b. Now, we will attempt to balance the tree after the values have been inserted. Implement these methods: i. int[] a sortedTree(); -- Outputs the tree in sorted order of an array. ii. BST balanceTreeOne(); -- Balances the tree by creating a new BST and inserting the values of the sorted array in a way such that the tree height is balanced. Linear insertion of the sorted values would be the worst possible height. c. During Red-Black Trees, we discussed the concept of rotations. Rotations of a node involve pushing a node to the left or right and reconnecting the parent/children nodes. Please see Slides 26-29 of the Balanced Search Tree lectures to see what occurs in rotations. Implement these methods for your BST: i. Node rotateRight(Node h) Rotates a given node h to the right and returns the new parent node after rotation. See the Slides for detail. 1. Note! You need to update the code here to cancel the function if there are no left subchildren! ii. Node rotateLeft(Node h) Rotates a given node h to the left and returns the new parent node after rotation. See the slides for detail. 1. Note! You need to update the code here to cancel the function is there are no right subchildren! iii. void transformToList(); -- Performs a series of right rotations on the BST until the BST is just a linked list oriented to the right. The logic is like so: 1. Begin at the root, and check if there are left subchildren. If there are, rotate the root to the right. 2. If the root *still* has left children after rotating, continue rotating right until there are no more left children at the root. 3. Move to the right. Check if this parent node has left children. If so, rotateRight on the parent. Continue doing so until there are no more left children. 4. Repeat all the way down until there are no more nodes that have left children. The tree is now a right-leaning linked list. d. We will now attempt to balance the BST without creating new memory, as we did in Part b. Implement these methods: i. void balanceTreeTwo(); -- Restructures the BST. It will do this by following this logic: 1. First, restructure the tree by calling transformToList(); to turn it into a right-leaning linked list. 2. Compute the parameter = ( + 1) 2 log2 . a. N is the total number of nodes, log2 means to compute the floor of log2 . 3. From the root of the tree (which is now a right-leaning linked list), perform left rotations on every odd node until odd nodes have been rotated. a. Example: Imagine a list 0->1->2->3->4. If = 2, then we perform rotateLeft() on the 0 node and the 2 node. Thats exactly odd nodes. 4. Compute the parameter = log2 1. 5. For K times, compute left rotations on the remaining right-leaning odd nodes. a. In the example list above, we did left rotations on 2 odd nodes. If we ignore the new left links and just look at the right links, we have 1->3->4. We would do left rotations on 1 and 4. 6. Congratulations, the tree is now balanced! e. Include a PDF, Problem2.PDF. Include these parts: i. How does the algorithm of balanceTreeTwo(); balance the tree -- why does this work? Explain it for all steps. ii. What is the total time complexity of the balanceTreeOne(); function in the average case? Consider how this function worked. balanceTreeOne(); first calls sortedTree(); then creates a new BST out of that. The cost of this should be () = () + (([])). You will fill this in for the actual values. iii. What is the space complexity of the balanceTreeOne(); function? iv. What is the total time complexity of the balanceTreeTwo(); function? Perform a similar analysis to I, where you sum up the cost of the internal operations. v. What is the space complexity of balanceTreeTwo();?