Insert

def getHeight(root):
    if not root:
        return 0
    return root.height


def getBalance(root):
    if not root:
        return 0
    return getHeight(root.left) - getHeight(root.right)


def leftRotate(root):
    right_son = root.right
    T2 = right_son.left

    right_son.left = root
    root.right = T2

    root.height = 1 + max(getHeight(root.left),
                       getHeight(root.right))
    right_son.height = 1 + max(getHeight(right_son.left),
                       getHeight(right_son.right))

    return right_son


def rightRotate(root):
    left_son = root.left
    T3 = left_son.right

    left_son.right = root
    root.left = T3

    root.height = 1 + max(getHeight(root.left),
                       getHeight(root.right))
    root.height = 1 + max(getHeight(left_son.left),
                       getHeight(left_son.right))

    return left_son


def insert(val, root):
    if not root:
        return Node(val)
    elif val < root.val:
        root.left = insert(val, root.left)
    else:
        root.right = insert(val, root.right)

    root.height = 1 + max(getHeight(root.left),
                          getHeight(root.right))

    balance = getBalance(root)

    if balance > 1 and val < root.left.val:
        return rightRotate(root)

    if balance < -1 and val > root.right.val:
        return leftRotate(root)

    if balance > 1 and val > root.left.val:
        root.left = leftRotate(root.left)
        return rightRotate(root)

    if balance < -1 and val < root.right.val:
        root.right = rightRotate(root.right)
        return leftRotate(root)

    return root