Operations on Trees 1. Operations on Binary Trees Binary trees with integer keys are implemented by the classes Tree and Node, defined as follows: class Tree\{ Node root; class Node\{ int key; Node left, right, parent; }, together with the method insert from the lecture. In this exercise, you are asked to develop additional methods on trees to this class. 1. boolean balanced(): returns true if the tree is balanced and no otherwise. For the balance check, we consider as leaves all null children of Node objects in the tree (as in the definition of red-black trees). A tree is is balanced if no two such leaf nodes differ in distance from the root by more than one. 2. Node floor (int x ): returns the rightmost node with respect to inorder traversal with a key that is less or equal to x; if no such node exists, it returns null; Provide two implementations, a recursive and an iterative one. 3. List keysAtDepth (int d): returns a linked list, which was implemented as a part of your Assignment 7, with exactly those integers that occur at depth d in the tree, ordered as they appear from left to right in the tree; if there are no nodes at depth d, return an empty list. Make sure that the algorithm is as efficient as possible, that is, look only at nodes with depth at most d and restrict list operations to one insertion per integer to be inserted. Hint: Note that there may be a name clash if you make the class Node of lists visible outside of List. 4. static Tree buildFromArray (int [ ] A): returns a tree of minimal height whose nodes contain as keys exactly the entries of the array A, in the same order (with respect to inorder traversal) as in the array. Tasks: - Write pseudocode for the four methods and possibly for auxiliary methods that you will need. Explain the ideas behind those methods. - Implement the methods within a Java class Tree. - Test your implementation and report on the tests. (15 Points) Instructions: Your assignment should represent your group effort. However, you are not expected to work alone. It is fine to discuss the exercises and try to find solutions together, but each student shall write down and submit his/her solutions separately. It is good academic standard to acknowledge collaborators, so if you worked together with other students, please list their names. You can write up your answers by hand (provided your handwriting is legible) or use a word processing system like Latex or Word. Experience shows that Word is in general difficult to use for this kind of task. For all programming tasks, it is not allowed to use any external libraries ("import") if not stated otherwise. Please, include Your name, student ID. Submission date: 15th January 2023