debug avl tree - python3 (not a solution)
i did not get it during the contest using the following avl tree structure (which should be more sophisticated than a preorder traversal but i ran out of time),
i did not get it during the contest using the following avl tree structure (which should be more sophisticated than a preorder traversal but i ran out of time), any idea on what went wrong? the avl tree is from geeks4geeks.\n```\nclass TreeNode:\n    def __init__(self, val):\n        self.val = val\n        self.left = None\n        self.right = None\n        self.height = 1\n        \n        \n# AVL tree class which supports insertion,\n# deletion operations\nclass AVL_Tree:\n  \n    def insert(self, root, key):\n          \n        # Step 1 - Perform normal BST\n        if not root:\n            return TreeNode(key)\n        elif key < root.val:\n            root.left = self.insert(root.left, key)\n        else:\n            root.right = self.insert(root.right, key)\n  \n        # Step 2 - Update the height of the \n        # ancestor node\n        root.height = 1 + max(self.getHeight(root.left),\n                          self.getHeight(root.right))\n  \n        # Step 3 - Get the balance factor\n        balance = self.getBalance(root)\n  \n        # Step 4 - If the node is unbalanced,\n        # then try out the 4 cases\n        # Case 1 - Left Left\n        if balance > 1 and key < root.left.val:\n            return self.rightRotate(root)\n  \n        # Case 2 - Right Right\n        if balance < -1 and key > root.right.val:\n            return self.leftRotate(root)\n  \n        # Case 3 - Left Right\n        if balance > 1 and key > root.left.val:\n            root.left = self.leftRotate(root.left)\n            return self.rightRotate(root)\n  \n        # Case 4 - Right Left\n        if balance < -1 and key < root.right.val:\n            root.right = self.rightRotate(root.right)\n            return self.leftRotate(root)\n  \n        return root\n  \n    # Recursive function to delete a node with\n    # given key from subtree with given root.\n    # It returns root of the modified subtree.\n    def delete(self, root, key):\n  \n        # Step 1 - Perform standard BST delete\n        if not root:\n            return root\n  \n        elif key < root.val:\n            root.left = self.delete(root.left, key)\n  \n        elif key > root.val:\n            root.right = self.delete(root.right, key)\n  \n        else:\n            if root.left is None:\n                temp = root.right\n                root = None\n                return temp\n  \n            elif root.right is None:\n                temp = root.left\n                root = None\n                return temp\n  \n            temp = self.getMinValueNode(root.right)\n            root.val = temp.val\n            root.right = self.delete(root.right,\n                                      temp.val)\n  \n        # If the tree has only one node,\n        # simply return it\n        if root is None:\n            return root\n  \n        # Step 2 - Update the height of the \n        # ancestor node\n        root.height = 1 + max(self.getHeight(root.left),\n                            self.getHeight(root.right))\n  \n        # Step 3 - Get the balance factor\n        balance = self.getBalance(root)\n  \n        # Step 4 - If the node is unbalanced, \n        # then try out the 4 cases\n        # Case 1 - Left Left\n        if balance > 1 and self.getBalance(root.left) >= 0:\n            return self.rightRotate(root)\n  \n        # Case 2 - Right Right\n        if balance < -1 and self.getBalance(root.right) <= 0:\n            return self.leftRotate(root)\n  \n        # Case 3 - Left Right\n        if balance > 1 and self.getBalance(root.left) < 0:\n            root.left = self.leftRotate(root.left)\n            return self.rightRotate(root)\n  \n        # Case 4 - Right Left\n        if balance < -1 and self.getBalance(root.right) > 0:\n            root.right = self.rightRotate(root.right)\n            return self.leftRotate(root)\n  \n        return root\n  \n    def leftRotate(self, z):\n  \n        y = z.right\n        T2 = y.left\n  \n        # Perform rotation\n        y.left = z\n        z.right = T2\n  \n        # Update heights\n        z.height = 1 + max(self.getHeight(z.left), \n                         self.getHeight(z.right))\n        y.height = 1 + max(self.getHeight(y.left), \n                         self.getHeight(y.right))\n  \n        # Return the new root\n        return y\n  \n    def rightRotate(self, z):\n  \n        y = z.left\n        T3 = y.right\n  \n        # Perform rotation\n        y.right = z\n        z.left = T3\n  \n        # Update heights\n        z.height = 1 + max(self.getHeight(z.left),\n                          self.getHeight(z.right))\n        y.height = 1 + max(self.getHeight(y.left),\n                          self.getHeight(y.right))\n  \n        # Return the new root\n        return y\n  \n    def getHeight(self, root):\n        if not root:\n            return 0\n  \n        return root.height\n  \n    def getBalance(self, root):\n        if not root:\n            return 0\n  \n        return self.getHeight(root.left) - self.getHeight(root.right)\n  \n    def getMinValueNode(self, root):\n        if root is None or root.left is None:\n            return root\n  \n        return self.getMinValueNode(root.left)\n  \n    def preOrder(self, root):\n        if not root:\n            return []\n        ans=[]\n        ans.extend(self.preOrder(root.left))\n        ans.append(root.val)\n        \n        ans.extend(self.preOrder(root.right))\n        return ans\n\n\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.stream=[]\n        self.tree=AVL_Tree()\n        self.root=None\n        self.m=m\n        self.k=k\n\n    def addElement(self, num: int) -> None:\n        \n        #maintain tree\n        self.root=self.tree.insert(self.root,num)\n        if len(self.stream)>self.m:\n            self.root=self.tree.delete(self.root,self.stream[-self.m])\n                \n        #maintain stream\n        self.stream.append(num)\n\n    def calculateMKAverage(self) -> int:\n        if len(self.stream)<self.m:\n            return -1\n        orderlist=self.tree.preOrder(self.root)\n        sellist=orderlist[self.k:-self.k]\n        return int(sum(sellist)/len(sellist))\n\n\n# Your MKAverage object will be instantiated and called as such:\n# obj = MKAverage(m, k)\n# obj.addElement(num)\n# param_2 = obj.calculateMKAverage()\n```\n![image](https://assets.leetcode.com/users/images/f5cfcb29-83b4-4708-8254-9dc0bd479e7c_1618114497.6006398.png)\n
[]