class AVLNode$($BSTNode$)$: $"""$ AVL Tree Node class. Inherits from BSTNode DO NOT CHANGE THIS CLASS IN ANY WAY $"""$ def $\_\_$init$\_\_($self$,$ value: object$)->$ None: $"""$ Initialize a new AVL node DO NOT CHANGE THIS METHOD IN ANY WAY $"""$ # call $\_\_$init$\_\_()$ from parent class super$().\_\_$init$\_\_($value$)$ # new variables needed for AVL self.parent $=$ None self.height $=0$ def $\_\_$str$\_\_($self$)->$ str: $"""$ Override string method DO NOT CHANGE THIS METHOD IN ANY WAY $"""$ return 'AVL Node: $\{\}\text{'}.$format$($self$.$value$)$ class AVL$($BST$)$: $"""$ AVL Tree class. Inherits from BST $"""$ def $\_\_$init$\_\_($self$,$ start$\_$tree$=$None$)->$ None: $"""$ Initialize a new AVL Tree DO NOT CHANGE THIS METHOD IN ANY WAY $"""$ # call $\_\_$init$\_\_()$ from parent class super$().\_\_$init$\_\_($start$\_$tree$)$ def $\_\_$str$\_\_($self$)->$ str: $"""$ Override string method DO NOT CHANGE THIS METHOD IN ANY WAY $"""$ values $=[]$ super$().\_$str$\_$helper$($self$.\_$root, values$)$ return "AVL pre$-$order $\{"+",".$join$($values$)+"\}"$ def is$\_$valid$\_$avl$($self$)->$ bool: $"""$ Perform pre$-$order traversal of the tree. Return False if there are any problems with attributes of any of the nodes in the tree. This is intended to be a troubleshooting 'helper' method to help find any inconsistencies in the tree after the add$()$ or remove$()$ operations. Review the code to understand what this method is checking and how it determines whether the AVL tree is correct. DO NOT CHANGE THIS METHOD IN ANY WAY $"""$ stack $=$ Stack$()$ stack.push$($self$.\_$root$)$ while not stack.is$\_$empty$()$: node $=$ stack.pop$()$ if node: # check for correct height $($relative to children$)$ left $=$ node.left.height if node.left else $-1$ right $=$ node.right.height if node.right else $-1$ if node.height $!=1+$ max$($left$,$ right$)$: return False if node.parent: # parent and child pointers are in sync if node.value $<$ node.parent.value: check$\_$node $=$ node.parent.left else: check$\_$node $=$ node.parent.right if check$\_$node $!=$ node: return False else: # NULL parent is only allowed on the root of the tree if node $!=$ self.$\_$root: return False stack.push$($node$.$right$)$ stack.push$($node$.$left$)$ return True # $------------------------------------------------------------------$ # def add$($self$,$ value: object$)->$ None: $"""$ TODO: Write your implementation $"""$ pass