$8\mathrm{.}14$ LAB: AVL tree Nth largest operationLAB ACTIVITY$8\mathrm{.}14\mathrm{.}1$: LAB: AVL tree Nth largest operation$0/10$Step $1$: Inspect the BSTNode.java and BinarySearchTree.java filesInspect the BSTNode class for a binary search tree node in BSTNode.java. The BSTNode class has private fields for the key, parent, left child, and right child. Accessor methods exist for each.Inspect the BinarySearchTree class declaration for a binary search tree in BinarySearchTree.java. The getNthKey$()$ method is the only abstract method that exists.Step $2$: Inspect other files related to the inheritance hierarchyClasses AVLNode and AVLTree extend 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.Step $3$: Understand the subtreeKeyCount field's purposeThe ExtendedAVLNode class inherits from AVLNode and adds the integer field subtreeKeyCount. Each node's subtree key count is the number of keys in the subtree rooted at that node. Ex:ExtendedAVLNode's constructor and getSubtreeKeyCount$()$ method are already implemented and should not be changed. Additional methods are needed to ensure that subtreeKeyCount remains accurate.Step $4$: Implement ExtendedAVLTree and ExtendedAVLNodeEach 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$()$ 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 getNthKey$()$ in this step. getNthKey$()$ requires correct subtree counts at each node.Step $5$: Run testsTreeTestCommand is an abstract base class defined in TreeCommands.java. A TreeTestCommand object is an executable command that operates on a binary search tree. Classes inheriting from TreeTestCommand are in their respective files:$*$ TreeInsertCommand 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 getNthKey$()$ returns an expected valueCode in Main.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,$ verify that the first two tests in Main.java pass. Then submit code and ensure that the first two unit tests pass.Step $6$: Implement ExtendedAVLTree's getNthKey$()$ methodgetNthKey$()$ 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.$Implement an algorithm that uses the subtree key counts so that getNthKey$()$ operates in worst case O$($log N$)$ time.