I wanted to get an understanding of different data structures and therefore implemented an AVL tree in python. However I somehow messed things up when it comes to insertion and therefore rotation.

If I run my module my terminal just spits out the root node and the node with value 3 for the first test and only the root for the second one. What is it I am doing wrong? I would appreciate another pairs of eyes as I miss the forest for the trees by trying to debug this 🙁

"""AVL-Tree implementation."""   class Node():     """Class representating an AVL node."""      __slots__ = ["data", "height", "key", "left", "right"]      def __init__(self, key, data=None):         """         Create new node.          :param {any} key: Key to use for operations.         :param {any} data: Payload to store.         """         self.data = [data]         self.height = 1         self.key = key         self.left = self.right = None      def __repr__(self):         """Return string representation."""         return "{} ({} => {})".format(self.height, self.key, self.data)  def get_height(node):     """     Return height for node.      :param {Node} node: Node to get height for.     """     return node.height if node else 0  def in_order(node):     """     Return node values in order.      :param {Node} node: Node to process.     """     if not node:         return     in_order(node.left)     print(node)     in_order(node.right)  def insert(node, key, data=None):     """     Insert new data.      :param {Node} node: Current node.     :param {any} key: Node key.     :param {any} data: Payload.     """     if not node:         return Node(key, data)     elif key == node.key:         node.data.append(data)         return node     elif key < node.key:         node.left = insert(node.left, key, data)     else:         node.right = insert(node.right, key, data)     left_height = get_height(node.left)     right_height = get_height(node.right)     node.height = max(left_height, right_height) + 1     balance = left_height - right_height     # Inbalance left     if balance == 2:         # left right => left left         if key > node.left.key:             node.left = rotate_left(node.left)         # left left         rotate_right(node)     # Inbalance right     elif balance == -2:         # right left => right right         if key < node.right.key:             node.right = rotate_right(node.right)         # right right         rotate_left(node)     return node  def pre_order(node):     """."""     if node:         print(node)         pre_order(node.left)         pre_order(node.right)  def rotate_left(node):     r"""     Left node rotation (balance == -2).      1 (node)      \            2       2     =>   / \        \        1   3         3      :param {Node} node: Node to rotate.     """     child = node.right     child.left, node.right = node, child.left     return node  def rotate_right(node):     r"""     Right node rotation.          3 (node)        /          2       2     =>   / \      /          1   3     1      :param {Node} node: Node to rotate on.     """     child = node.left     child.right, node.left = node, child.right     return node   if __name__ == "__main__":     root = Node(0)     for i in range(1, 4):         root = insert(root, i)     in_order(root)     print(".....")     root2 = Node(0)             for i in range(1, 4):         root2 = insert(root, i)     in_order(root2) 

Thank you for your help!