Questionl. Array List based implementation of a Binary Tree: We would like to implement a Binary Tree with nodes containing distinct values using an Array List implemented in java.util.ArrayList. We will use the same strategy shown in class: For a node stored at index i of the Array List we store its left child at index 2i and its right child at index 2i +1. The addition, removal and retireval of nodes in the tree is accomplished using the values stored in the nodes. For example, if we want to add a String "AB" in the tree as left child of String "AA" we use AddLeftChild ("AA", "AB") Implement the following methods of the generic class BinaryTree using the methods of java.util.ArrayList as well as any other method you find necessary: public void AddRoot (T Value): Adds the non NULL node/Object Value at the root of the tree; The tree should be empty else return error public void AddLeftChild(T Parent, T Value): Adds the node/Object Value as left child of Parent; The node/Object Parent should be in the tree and different than NULL, else return error. Make sure that you fill the non used elements of the ArrayList with NULL . public void AddRightChild(T Parent, T Value): Adds the node/Object Value as right child of Parent; The node/Object Parent should be in the tree and different than NULL, else return error. Make sure that you fill the non used elements of the Array List with NULL public void RemoveNode (T Value): Recursively removes the node/Object Value and all its sub-trees from the tree; You should verify that the node/Object Value is already in the tree and different than NULL, else return error public void ReplaceNode (T Value1,T Value2): Replaces the node/Object Valuel by the non NULL node/Object Value2. You should verify that the node/Object Value1 is already in the tree and different than NULL, else return error public boolean Exists (T Value): Indicates if the non NULL node/Object Value is in the tree public boolean IsRoot (T Value) Indicates if the non NULL node/Object Value is the root of the tree public boolean HasLeft (T Value): Indicates if the node/Object Value has a left child in the tree. You should verify that the node/Object Value is already in the tree and different than NULL, else return error public boolean HasRight (T Value): Indicates if the node/Object Value has a right child in the tree. You should verify that the node/Object Value is already in the tree and different than NULL, else return error . public boolean HasChildren (T Value): Indicates if the node/Object Value has children in the tree. You should verify that the node/Object Value is already in the tree and different than NULL, else return error public T GetLeft (T Value): Returns the non NULL node/Object left child of Value if it exists in the tree. You should verify that the node/Object Value is already in the tree and different than NULL, else return error public T GetRight (T Value): Returns the non NULL node/Object right child of Value if it exists in the tree. You should verify that the node/Object Value is al- ready in the tree and different than NULL, else return error public T GetParent (T Value): Returns the node/Object parent of Value. You should verify that the node/Object Value is already in the tree, is not the root, and different than NULL, else return error . public T GetRoot (): Returns the non NULL node/Object at the root of the tree Question2. Linked List based implementations of Queues: generic LinkedList implemented by java.util.LinkedList Question3. Iterative level-order traversal of a binary tree: Implement the basic methods of the ADT Queue (enqueue, dequeue, first etc.) using a Using an auxiliary queue propose an iterative algorithm to print out the values stocked in a tree read following a level order traversal. Implement this algorithm Leve1Order ) in your BinaryTree class. Test : stocked values following a level order traversal. Test your class and methods by implementing the following binary tree and printing out the BA NG LEG EN -DA RY