Step $6$: Implement ExtendedAVLTree's get$\_$nth$\_$key$()$ method $($worst case O$($log n$))$

get$\_$nth$\_$key$()$ 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 get$\_$nth$\_$key$(0)$ returns $10,$ get$\_$nth$\_$key$(1)$ returns $19,...,$ get$\_$nth$\_$key$(5)$ returns $55,$ and get$\_$nth$\_$key$(6)$ returns $77.$

Determine an algorithm that uses the subtree key counts so that get$\_$nth$\_$key$()$ operates in worst case O$($log n$)$ time.