PYTHON $3--$ AVL tree$-$ please do the add$()$ function. Existing skeleton code cannot be altered, but helper methods can be added. NO BUILT$-$IN DATA STRUCTURES CAN BE USED. Instructions for add$()$ are attached along with skeleton code. Please make sure that the given test code works.

add$($self$,$ value: object$)->$ None:

This method adds a new value to the tree while maintaining its AVL property. Duplicate

valu

Skeleton Code:

class Stack:

$"""$

Class implementing STACK ADT.

Supported methods are: push, pop, top, is$\_$empty

DO NOT CHANGE THIS CLASS IN ANY WAY

YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION

$"""$

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

$"""$ Initialize empty stack based on Python list $"""$

self.$\_$data $=[]$

def push$($self$,$ value: object$)->$ None:

$"""$ Add new element on top of the stack $"""$

self.$\_$data.append$($value$)$

def pop$($self$)$:

$"""$ Remove element from top of the stack and return its value $"""$

return self.$\_$data.pop$()$

def top$($self$)$:

$"""$ Return value of top element without removing from stack $"""$

return self.$\_$data$[-1]$

def is$\_$empty$($self$)$:

$"""$ Return True if the stack is empty, return False otherwise $"""$

return len$($self$.\_$data$)==0$

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

$"""$ Return content of the stack as a string $($for use with print$)"""$

data$\_$str $=[$str$($i$)$ for i in self.$\_$data$]$

return "STACK: $\{"+",".$join$($data$\_$str$)+"\}"$

class Queue:

$"""$

Class implementing QUEUE ADT.

Supported methods are: enqueue, dequeue, is$\_$empty

DO NOT CHANGE THIS CLASS IN ANY WAY

YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION

$"""$

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

$"""$ Initialize empty queue based on Python list $"""$

self.$\_$data $=[]$

def enqueue$($self$,$ value: object$)->$ None:

$"""$ Add new element to the end of the queue $"""$

self.$\_$data.append$($value$)$

def dequeue$($self$)$:

$"""$ Remove element from the beginning of the queue and return its value $"""$

return self.$\_$data.pop$(0)$

def is$\_$empty$($self$)$:

$"""$ Return True if the queue is empty, return False otherwise $"""$

return len$($self$.\_$data$)==0$

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

$"""$ Return content of the stack as a string $($for use with print$)"""$

data$\_$str $=[$str$($i$)$ for i in self.$\_$data$]$

return "QUEUE $\{"+",".$join$($data$\_$str$)+"\}"$

class TreeNode:

$"""$

AVL Tree Node class

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

$"""$

self.value $=$ value

self.left $=$ None

self.right $=$ None

self.parent $=$ None

self.height $=0$

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

return 'AVL Node: $\{\}\text{'}.$format$($self$.$value$)$

class AVL:

def $\_\_$init$\_\_($self$,$ start$\_$tree$=$None$)->$ None:

$"""$

Initialize a new AVL tree

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

self.root $=$ None

# populate AVL with initial values $($if provided$)$

# before using this feature, implement add$()$ method

if start$\_$tree is not None:

for value in start$\_$tree:

self.add$($value$)$

def $\_\_$str$\_\_($self$)->$ str:

$"""$

Return content of AVL in human$-$readable form using pre$-$order traversal

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

values $=[]$

self.$\_$str$\_$helper$($self$.$root, values$)$

return "AVL pre$-$order $\{"+",".$join$($values$)+"\}"$

def $\_$str$\_$helper$($self$,$ cur, values$)$:

$"""$

Helper method for $\_\_$str$\_\_.$ Does pre$-$order traversal

DO NOT CHANGE THIS METHOD IN ANY WAY

$"""$

if cur:

values.append$($str$($cur$.$value$))$

self.$\_$str$\_$helper$($cur$.$left, values$)$

self.$\_$str$\_$helper$($cur$.$right, 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

$"""$

s $=$ Stack$()$

s$.$push$($self$.$root$)$

while not s$.$is$\_$empty$()$:

node $=$ s$.$pop$()$

if node:

# check for correct height $($relative to children$)$

l $=$ node.left.height if node.left else $-1$

r $=$ node.right.height if node.right else $-1$

if node.height $!=1+$ max$($l$,$ r$)$:

return False

if node.parent:

# parent and child pointers are in sync

if node.value $$ node.par