write java code only where it indicates "Your code here" in ExtendedAVLNode.java and ExtendedAVLTree.java

Step 1: Inspect the BSTNode.java and BinarySearchTree.java files Inspect the BSTNode class declaration for a binary search tree node in BSTNode.java. Access BSTNode.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. The BSTNode class has private fields for the key, parent reference, left child reference, and right child reference. Accessor methods exist for each. Inspect the BinarySearchTree class declaration for a binary search tree node in BinarySearchTree.java. The getNthKey0 method is the only abstract method that exists. Step 2: Inspect other files related to the inheritance hierarchy Classes AVLNode and AVLTree inherit from BSTNode and BinarySearchTree, respectively. Each class is implemented in a read only file. Classes ExtendedAVLNode and ExtendedAVLTree are declared, but implementations are incomplete. Both classes must be implemented in this lab. Read only, completed class implementation Incomplete class implementation Step 3: Understand the purpose of the subtreeKeyCount variable The ExtendedAVLNode class inherits from AVLNode and adds one integer field, subtreeKeyCount. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex: y count ExtendedAVLNode's constructor and getSubtreeKeyCount 0 methods are already implemented and should not be changed. Additional methods are needed to ensure that subtreeKeyCount remains accurate. Step 4: Implement ExtendedAVLI ree and ExtendedAVLNode Each node in an ExtendedAVLTree must have a correct subtreeKeyCount after an insertion or removal operation. Determine which methods in AVLTree and AVLNode must be overridden in ExtendedAVLTree and ExtendedAVLNode to keep each node's subtreeKeyCount correct. New methods can be added along with overridden methods, if desired. Hint: Consider an updateSubtreeKeyCount 0 method for the ExtendedAVLNode class. The method requires each child node's subtreeKeyCount to be correct, and updates the node's subtreeKeyCount appropriately. Overridden methods in both ExtendedAVLNode and ExtendedAVLTree can call a node's updateSubtreeKeyCount() method as needed. Once determinations are made, complete the implementation of both the ExtendedAVLTree and ExtendedAVLNode classes. Do not implement ExtendedAVLTree's getNthKey0 in this step. getNthKey0 requires correct subtree counts at each node. Step 5: Run tests in develop mode and submit mode TreeTestCommand is an abstract base class defined in TreeTestCommand.java. A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are declared in their respective files: - TreelnsertCommand inserts keys into the tree - TreeRemoveCommand removes keys from the tree - TreeVerifyKeysCommand verifies the tree's keys using an inorder traversal - TreeVerifySubtreeCountsCommand verifies that each node in the tree has the expected subtree key count - TreeGetNthCommand verifies that getNthKey0 returns an expected value Code in LabProgram.java contains three automated test cases. Each test executes an ArrayList of TreeTestCommand objects in sequence. The third test includes TreeGetNthCommands and will not pass until the completion of Step 6. The first two tests should pass after completion of step 4. Before proceeding to Step 6, run code in develop mode and ensure that the first two tests in LabProgram.java pass. Then submit code and ensure that the first two unit tests pass. Step 6: Implement ExtendedAVLTree's getNthKey() method (worst case O(log n) ) getNthKey0 must return the tree's nth-largest key. The parameter n starts at 0 for the smallest key in the tree. Ex: Suppose a tree has keys: 10,19,20,30,42,55,77 Then getNthKey (0) returns 10 , getNthKey (1) returns 19,., getNthKey (5) returns 55 , and getNthKey (6) returns 77. Determine an algorithm that uses the subtree key counts so that getNthKey 0 operates in worst case O(log n) time. 459428.3119604.qx3zqy7 protected BSTNode root; protected boolean in0rder(BSTNodeVisitor visitor, BSTNode current) \{ if (current != null) \{ // Visit left subtree first, if left child is non-null BSTNode left = current.getLeft(); if (left != null) \{ if (! in0rder(visitor, left)) \{ return false; \} // Visit the current node. Return false if the visitor method // returns false. if (!visitor.visit(current)) \{ return false; \} // Visit right subtree last, if right child is non-null BSTNode right = current.getRight (); if (right != null) \{ return true; \} // Inserts the node into the tree using the standard BST insertion algorithm protected void insertNode(BSTNode node) \{ // Check if tree is empty if ( root == null) root = node; \} else \{ BSTNode currentNode = root; while (currentNode != null) \{ // Choose to go left or right if (node.getKey () keysToRemove = new ArrayList (); public TreeRemoveCommand(ArrayList keys) \{ this. keysToRemove = new ArrayList (keys); \} a0verride public boolean execute(BinarySearchTree tree, PrintWriter testFeedback) \{ if (keysToRemove. size ( ) >0 ) \{ // Begin feedback message and remove first key testFeedback.write("Removing keys:" + keysToRemove.get () ); tree. removeKey (keysToRemove.get ( 0) ); // Remove remaining keys for (int i=1;i expectedPairs = new ArrayList (); oublic TreeVerifySubtreeCountsCommand(Arraylist> expectedKeyCountPairs) \{ expectedPairs = new ArrayList> (expectedKeyCountPairs); averride jublic boolean execute(BinarySearchTree tree, PrintWriter testFeedback) \{ // Create a BSTNodeVectorVisitor and do an in order traversal BSTNodeArrayListVisitor visitor = new BSTNodeArrayListVisitor(); tree.in0rder(visitor); I/ Compare actual to expected boolean passed = true; if (visitor.visitedNodes.size () == expectedPairs.size()) \{ for (int i=0;i