this failed test comes up when I test get$\_$nth$\_$key: FAIL: Check visited nodes for get$\_$nth$\_$key$(0)$ call: Step $4$: Implement ExtendedAVLTree and

ExtendedAVLNode

Each node in an ExtendedAVLTree must have a correct subtree$\_$key$\_$count 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

subtree$\_$key$\_$count correct. New methods can be added along with overridden

methods, if

Expected: $[61,38,12,9]$

Actual: $[]$ and more. this is my extendedAVLtree.py$.$ please change get nth$\_$key ans get$\_$nth$\_$key$\_$helper, so they both are able to correct this error:

from AVLTree import AVLTree

from ExtendedAVLNode import ExtendedAVLNode

class ExtendedAVLTree$($AVLTree$)$:

def $\_\_$init$\_\_($self$)$:

super$().\_\_$init$\_\_()$

def make$\_$new$\_$node$($self$,$ key$)$:

return ExtendedAVLNode$($key$)$

def insert$\_$node$($self$,$ node$)$:

super$().$insert$\_$node$($node$)$

# Update counts from node to root

while node:

node.update$\_$subtree$\_$key$\_$count$()$

node $=$ node.parent

def remove$\_$node$($self$,$ node$\_$to$\_$remove$)$:

parent $=$ node$\_$to$\_$remove.parent if node$\_$to$\_$remove else None

successful $=$ super$().$remove$\_$node$($node$\_$to$\_$remove$)$

# Update counts from parent to root after removal if successful

if successful and parent:

while parent:

parent.update$\_$subtree$\_$key$\_$count$()$

parent $=$ parent.parent

return successful

def get$\_$nth$\_$key$($self$,$ n$)$:

if self.root is None:

return $-1$ # Tree is empty, so n is out of bounds

result, node, visited $=$ self.$\_$get$\_$nth$\_$key$\_$helper$($self$.$root, n$)$

print$("$Visited nodes:", visited$)$

return result if node else $-1$ # Return $-1$ if the node is None $($n is out of bounds$)$

def $\_$get$\_$nth$\_$key$\_$helper$($self$,$ node, n$,$ visited$=$None$)$:

if visited is None:

visited $=[]$

if not node:

print$($f$"$Reached a None node, index $\{$n$\},$ visited nodes so far: $\{$visited$\}")$ # Debug

return None, None, visited

left$\_$size $=$ node.left.subtree$\_$key$\_$count if node.left else $0$

right$\_$size $=$ node.right.subtree$\_$key$\_$count if node.right else $0$

print$($f$"$Visiting node $\{$node$.$key$\}$ with left$\_$size $\{$left$\_$size$\},$ right$\_$size $\{$right$\_$size$\},$ searching for index $\{$n$\}")$ # Debug

visited.append$($node$.$key$)$ # Track visited nodes

if n $<$ left$\_$size:

return self.$\_$get$\_$nth$\_$key$\_$helper$($node$.$left, n$,$ visited$)$

elif n $==$ left$\_$size:

print$($f$"$Found node: $\{$node$.$key$\}$ at index $\{$n$\},$ path taken: $\{$visited$\}")$

return node.key, node, visited

else:

return self.$\_$get$\_$nth$\_$key$\_$helper$($node$.$right, n $-$ left$\_$size $-1,$ visited$)$

$\text{'}\text{'}\text{'}$

def get$\_$nth$\_$key$($self$,$ n$)$:

if self.root is None:

return $-1$ # Tree is empty, so n is out of bounds

result, node, visited $=$ self.$\_$get$\_$nth$\_$key$\_$helper$($self$.$root, n$)$

# Now 'visited' contains the list of visited node keys

# Here, you could potentially handle the 'visited' list depending on your requirement:

# For example, you could print it or check it against expected values in tests

print$("$Visited nodes:", visited$)$ # Example of usage

return result if node else $-1$ # Return $-1$ if the node is None $($n is out of bounds$)$

$\text{'}\text{'}\text{'}$

def $\_$get$\_$nth$\_$key$\_$helper$($self$,$ node, n$,$ visited$=$None$)$:

if visited is None:

visited $=[]$

if not node:

print$("$Reached a None node, returning."$)$ # Debug

return None,None,visited

left$\_$size $=$ node.left.subtree$\_$key$\_$count if node.left else $0$

right$\_$size $=$ node.right.subtree$\_$key$\_$count if node.right else $0$

print$($f$"$Visiting node $\{$node$.$key$\}$ with left$\_$size $\{$left$\_$size$\},$ right$\_$size $\{$right$\_$size$\},$ searching for index $\{$n$\}")$ # Debug

# Add the current node key to the visited list

visited.append$($node$.$key$)$

if n $<$ left$\_$size:

return self.$\_$get$\_$nth$\_$key$\_$helper$($node$.$left, n$,$ visited$)$

elif n $==$ left$\_$size:

return node.key,node,visited

else:

return self.$\_$get$\_$nth$\_$key$\_$helper$($node$.$right, n $-$ left$\_$size $-1,$ visited$)$

$\text{'}\text{'}\text{'}$

def get$\_$nth$\_$key$($self$,$ n$)$:

# Check if the request is within the bounds of existing tree keys

if n $<0$ or n $>=($self$.$root.subtree$\_$key$\_$count if self.root else $0)$:

return None # n is out of bounds

return self.$\_$get$\_$nth$\_$key$\_$helper$($self$.$root, n$)$

def $\_$get$\_$nth$\_$key$\_$helper$($self$,$ node, n$)$:

if not node:

return None

left$\_$size $=$ node.left.subtree$\_$key$\_$count if node.left else $0$

if n $<$ left$\_$size:

return self.$\_$get$\_$nth$\_$key$\_$helper$($node$.$left, n$)$

elif n $>$ left$\_$size:

return self.$\_$get$\_$nth$\_$key$\_$helper$($node$.$right, n $-$ left$\_$size $-1)$

else:

return node.key

$\text{'}$