please write code ONLY in ExtendedAVLNode.java and ExtendedAVLTree.java. all other code must remain the same. thanks

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 BSTNode successorNode = nodeToRemove. getRight () ; while (successorNode.getLeft () != null) \{ successorNode = successorNode. getLeft(); \} // Copy the key from the node nodeToRemove. setKey ( successorNode. getKey ()); I/ Recursively remove successor removeNode( successorNode); // Nothing left to do since the recursive call will have rebalanced return true; \} // Case 2: Root node (with 1 or 0 children) else if (nodeToRemove == root) \{ if (nodeToRemove.getLeft () != null) \{ root = (AVLNode) nodeToRemove.getLeft () ; \} else \{ \} if (root != null) \{ \} nodeToRemove = null; return true; \} // Case 3: Internal with left child only else if (nodeToRemove.getLeft() != null) \{ parent. replaceChild (nodeToRemove, nodeToRemove.getLeft ()); \} // Case 4: Internal with right child only OR leaf else \{ parent. replaceChild (nodeToRemove, nodeToRemove.getRight()); \} // nodeToRemove is removed from the tree and can be deleted nodeToRemove = null; I/ Anything that was below nodeToRemove that has persisted is already // correctly balanced, but ancestors of nodeToRemove may need rebalancing. AVLNode nodeToRebalance = (AVLNode) parent; while (nodeToRebalance != null) \{ rebalance(nodeToRebalance); nodeToRebalance =( AVLNode) nodeToRebalance.getParent () ; 3 return true; ride cted boolean removeNode(BSTNode nodeToRemove) \{ return removeAVLNode( (AVLNode) nodeToRemove); C AVLTree( \{ // Note: Parent class's constructor does all needed work ride C int getNthKey(int n ) \{ // Note: The ExtendedAVLTree.java implementation of // getNthKey() should override this. return 0 ; ublic class ExtendedAVLTree extends AVLTree \{ // Each node in an ExtendedAVLTree is an ExtendedAVLNode Qoverride protected BSTNode makeNewNode(int key) \{ return new ExtendedAVLNode(key); // Your code here QOverride public int getNthKey (int n){ // Your code here (remove placeholder line below) return 0; public abstract class BSTNodeVisitor \{ /I Returns true to continue traversal, false to terminate public abstract boolean visit(BSTNode node); \} import java.io. PrintWriter; // TreeTestCommand is the abstract base class for a command that tests some // aspect of a BinarySearchTree object public abstract class TreeTestCommand public abstract boolean execute(BinarySearchTree tree, PrintWriter testFeedback); \} mport java.io. PrintWriter; / TreeRemoveCommand removes an Arraylist of keys from the tree when executed ublic class TreeRemoveCommand extends TreeTestCommand \{ private ArrayList 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